วันศุกร์ที่ 24 มิถุนายน พ.ศ. 2559

Project Euler 003 - Largest Prime factor - การหา prime factor ที่ใหญ่ที่สุด

โจทย์จาก : https://www.hackerrank.com/contests/projecteuler/challenges/euler003

โจทย์ข้อนี้ต้องการให้เราหาจำนวนเฉพาะที่ใหญ่ที่สุด และเป็นตัวประกอบของ N โดย
ที่ 10 <=N<= 10^12 
แนวคิด เมื่อผมเห็นข้อนี้ สิ่งที่ผมคิดไว้ตอนแรกคือการรันลูปไล่ตั้งแต่ 2 จนถึง N/2 เพื่อหาตัวที่หารลงตัว เมื่อได้ตัวที่หารลงตัว ก็นำไปเช็คต่อว่าเป็นจำนวนเฉพาะไหม แต่ถ้าลองคิดดีๆแล้วการที่ N มีค่าเยอะๆ แล้ว factor ของ N มีจำนวนเฉพาะที่ค่าเยอะ ก็จะเสียเวลาในการเช็คอย่างมาก ผมก็เลยนึกถึงการหา factor สมัยตอนมัธยมต้น เพราะเนื่องจากจำนวนเต็มบวกสามารถเขียนอยู่ในรูปผลคูณ
ของจำนวนเฉพาะได้



จากรูปด้านบน คือการหา factor ของ 160 เราเริ่มจากเอา 2 ซึ่งเป็นจำนวนเฉพาะที่เล็กที่สุด ที่สามารถหาร 160 ได้ไปหารจนกว่าจะหารไม่ได้ หากเราทำการหารด้วยจำนวนเฉพาะจนกว่าจะหารไม่ได้ไปเรื่อยๆแล้วๆ สุดท้ายแล้วเราก็จะได้จำนวนเฉพาะที่ใหญ่ที่สุดออกมา (จำนวนเฉพาะที่เล็กที่สุด ของจำนวนประกอบ N ใดๆ จะมีค่าน้อยกว่าหรือเท่ากับ sqrt(N))

เราสามารถนำแนวคิดนี้ไปเขียนเป็นโค้ดในภาษาซีได้แบบนี้


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int n,ans = 0;
scanf("%d",&n);
for( int i = 2;i<=sqrt(n);i++)
{
while(n%i == 0)
{
n/=i;
ans = i;
}
}
if(n>1)
ans = n;
printf("%d",ans);
return 0;
}
view raw PFf.c hosted with ❤ by GitHub

ไม่มีความคิดเห็น:

แสดงความคิดเห็น