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


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
z = n/i

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


  1. I am solving Eulers Problems with a focus on Simplicity. I went back to the school days method of finding the prime factors of a number. continuous division.The code cant be simpler
    # n = number in question , c = factor , f = greatest facor

    if(n%c == 0):n,f=n/c,c
    print f


  2. firstly, you need not extract all the 2s.

    secondly you can always start first guess from the smallest prime number greater than greatest interger function ( sqrt (n)).

  3. I had some reason for not using the sqrt method but i forget