Monday, August 3, 2009

Greatest prime factor of a number: Project Euler Problem 3 in python

I think this converges fairly fast and is also based on the additive nature of primal factors. Further , it kind of leads into why primes get rarer (and hence this can be use to converge to prime factors)

Algorithm explained
Start with the smallest prime(p=2) and divide the evil number (e)
If it divides, extract he largest power of 2 from e possible.
--The divisor now is divisible by a prime factor greater than 2 and can utmost be e/2^i
--increment p to 3 and so on. Also check if e/3 is less than 3. This forms the outer limit

If the smallest prime (p=2) does not divide the number (e), even better for us
-- The number is divisible by something greater than 2 and hence, the other factor is less than e/2.
-- increment p by 1 and check if less than e/2. redo from 1st step

Heres the program,

# Problem 3 - to find the largest prime factor of a number

n= 600851475143

z=n

i = gcf = 2
while i <>
if n%i == 0:
x = 1
while (n%(i**x)) == 0:
x = x + 1
z =n/(i**(x-1))
n = z
gcf = z
print i," power ",x-1, " and other divisor is ", z
else:
z = n/i
gcf=n
i=i+1

print "The program is complete and the gratest prime factor is ", gcf