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. 001.png

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

002.png

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

Recommended Posts

What is Project Euler 3 Acceleration?
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler 37
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 26
Project Euler 8
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
What is namespace
What is copy.copy ()
What is dotenv?
What is Linux
What is klass?
What is SALOME?
What is Linux?
What is Linux
What is pyvenv
What is __call__
What is Linux
What is Python
What is a distribution?
What is Piotroski's F-Score?
What is Raspberry Pi?
[Python] What is Pipeline ...
What is Calmar Ratio?
What is a terminal?
[PyTorch Tutorial ①] What is PyTorch?
What is a hacker?
What is JSON? .. [Note]
What is Linux for?
What is a pointer?
What is ensemble learning?
What is TCP / IP?
What is Python's __init__.py?