Project Euler 3 고속화란?

13195의 소인수는 5, 7, 13, 29입니다.

600851475143의 가장 큰 요인 중 하나를 찾습니다.
ㅡㅡㅡ//오…사쿠라. 네. jp/p로지ぇc테우ぇr/그리고 x. php? cmd=레아 d&파게=P로 bぇm%203

마음껏 풀어 보았다.

target = 600851475143
i = 1
while target != 1:
  i += 2
  while not target % i:
    target /= i
print i

이것은 600851475143이 합성수임을 전제로 한 대답이다. 합성수이기 때문에 while 문장도 그렇게 반복되는 것은 아니다. 따라서 이 코드에서도 문제는 없다.
단, 600851475143이 소수인 경우, 이 코드에는 문제가 발생하게 된다. 600851475143/2 약 3조회정 잉여를 계산하게 된다.

즉, 다음과 같은 슈츄에이션이 발생한다.


서비스 제공에 있어서는 빠르고 문제가 되지 않고, 느리면 문제가 되기 쉽다. 이러한 관점에서 보면, 소수라도 위험 위험 회피의 관점에서 그 지연을 피할 수있는 다음과 같은 코드가 선호 될 수 있습니다.
다음의 코드에서는 엘라토스테네스의 체모로 target의 제곱근까지 소수의 리스트를 작성해, 그 리스트를 기초로 소인수 분해를 시도하고 있다. 모든 소수로 잉여계산을 하지 않는 점, target의 제곱근까지 밖에 계산을 하지 않는 점에서 안정된 처리속도가 나오지 않을까 생각된다. (target의 제곱근까지밖에 계산을 하지 않는 것은 위의 코드라도 할 수 있지만.)

import mymath
import math
target = 600851475143
pri = mymath.get_primes(int(math.sqrt(target)))
max_p = 1
for p in pri['list']:
    while not target % p:
        target /= p
        max_p = p
if target != 1:
    print target
else:
    print max_p

덧붙여 mymath는 이쪽.
h tp // w w. 사토파 t. 이. jp/