**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

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

ReplyDelete# n = number in question , c = factor , f = greatest facor

n,c,f=600851475143,2,2

while(c<=n):

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

else:c=c+1

print f

#dhruba

firstly, you need not extract all the 2s.

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

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

ReplyDelete