[PYTHON] What is Project Euler 3 Acceleration?

The prime factors of 13195 are 5, 7, 13, 29.

Find the largest prime factor of 600851475143. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

I tried to solve it as I came up with it.

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

This is an answer assuming that 600851475143 is a composite number. The while statement is not repeated so much because it is a composite number. Therefore, there is no problem with this code. However, if 600851475143 is a prime number, this code will have problems. 600851475143/2 The remainder will be calculated about 3 trillion times.

In other words, the following situations will occur.

In service provision, it is not a problem at an early stage, and it tends to be a problem at a late time. From this point of view, even if it is a prime number, the following code that can avoid the slowness from the viewpoint of risk hedging may be preferable. In the following code, a list of prime numbers is created up to the square root of the target using the Eratosthenes sieve, and the prime factorization is attempted based on the list. It seems that stable processing speed can be obtained in that the remainder calculation is not performed for all prime numbers and that the calculation is performed only up to the square root of the target. (Although the above code can only calculate up to the square root of 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

Click here for mymath. http://www.sato-pat.co.jp/