Loading ...Problem Description
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Analysis
The request to find the prime factors of a number comes up much too often. To satisfy these requests we wrote a small javascript program that can be accessed here: prime factor calculator. It can easily handle numbers up to 16 digits long in an instant.
The solution below is the essence of that script.
Solution
Runs < 1 second in Python.
def lpf(n): if n < 2: return False for p in (2,3): while n % p == 0: n /= p if n == 1: return p p = 5; fl = 1 while (p*p<=n): while n % p == 0: n /= p if n == 1: return p p+= 3-fl fl = -fl return n print "Answer to PE3 = ",lpf(600851475143)
from euler impot is_prime
f, pr, n = 3, 1, 600851475143
>while pr != n:
if n%f == 0 and is_pr(f): pr *= f
f += 2
>f-2
_______________
Much shorter and as fast as yours.
Yes, this is some very nice code. I may have to change my solution to include your program. I think yours is much easier to understand. Thanks for the suggestion.