Python Implementation of Problem 3

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 3

More lazy functions this time. Took a little while to figure out how to eliminate the special case for 2.

Revision 1:

I changed the implementation of prime_factors() to stop checking if factors exceed the square root of the number. This eliminates a lot of checking for numbers which could not possibly be the factor.

Revision 2:

Changed prime_factors to catch accidental 0s and -1s, further optimize sqrt checks, and added a persistant cache of primes to reduce the space that needs checking

Revision 3:

Move primes() to p0003 in order to fix caching. Switch to a prime number sieve for generating new primes for the cache.

Problem:

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

What is the largest prime factor of the number 600851475143 ?

python.src.p0003.main() → int
 1"""
 2Project Euler Problem 3
 3
 4More lazy functions this time. Took a little while to figure out how to
 5eliminate the special case for 2.
 6
 7Revision 1:
 8
 9I changed the implementation of prime_factors() to stop checking if factors
10exceed the square root of the number. This eliminates a lot of checking for
11numbers which could not possibly be the factor.
12
13Revision 2:
14
15Changed prime_factors to catch accidental 0s and -1s, further optimize sqrt
16checks, and added a persistant cache of primes to reduce the space that needs
17checking
18
19Revision 3:
20
21Move primes() to p0003 in order to fix caching. Switch to a prime number sieve
22for generating new primes for the cache.
23
24Problem:
25
26The prime factors of 13195 are 5, 7, 13 and 29.
27
28What is the largest prime factor of the number 600851475143 ?
29"""
30from .lib.primes import prime_factors
31
32
33def main() -> int:
34    return max(prime_factors(600851475143))

Tags: prime-number, factorization, python-iterator