[Scratch] _ Project Euler #003 _ Largest Prime Factor (최대 소인수)

Problem 3.

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

주어진 수의 소인수 중, 최대값 구하기.

 

 

참고로, factor 찾을때마다 덮어쓰면서 갱신하지 않고 list 에 저장하고,
나눠서 소모시킬때마다 또다른 list 저장하면, 소인수분해하는 코드가 됨.

NOTE:
나누기를 시도하는 숫자를 어떻게 점프시키느냐로 약간의 효율성을 높일수 있음. 가령 모든 짝수는 건너뛰고, 또 3의 배수도 건너뛰고, 그래서 6n-1, 6n+1 꼴만 체크한다던가... 근데 그정도론 order 자체를 바꿀정도는 아님. 차라리 체크범위를 가령 sqrt N 으로 줄여준다던가 하는게 수가 커질수록 이득.