What is the largest prime factor of the number 600851475143 ?

this gives answer 1471 second greatest

if i try i<=N it gives correct answer

Actually Jesper Young wrote somewhere this -- instead of testing all numbers between 2 and N, you only need to test all primes between 2 and the square root of N.

also i read from somewhere this

A prime number has only two distinct factors, 1 and itself, clearly the number itself is greater than the square root of itself.
Given n and a (which is a factor of n), then n / a is also a factor of n.
For example if n = 777 and a = 37, then 777 / 37 = 21 is also a factor of 777 as 777 / 21 = 37.
Suppose we have a factor b which is greater than the square root of n:

b > sqrt(n)
1 / b < 1 / sqrt(n) // inverse
n / b < n / sqrt(n) // multiply by n
n / b < sqrt(n) // cancel n1 / n0.5 = n0.5 = sqrt(n)

This shows that if we have some factor b greater than the square root of n then there must exist factors less than the square root of n also, therefore if we do NOT have any factors less than the square root of n then by contradiction we CANNOT have an factors greater than than the square root of n.

Your program ignores the largest prime factor for some reason.

Try debugging it (or analyze what it does) for some small N (e.g. N=15 or N=60) to find out why.

harish thiru
Ranch Hand

Joined: Aug 02, 2008
Posts: 32

posted

0

Vlado Zajac i tried debugging before also
I get there is something wrong in the algorithm but i am thinking what Jesper Young was saying

i understood that there are prime factors greater than square root of n, but if you don't find one before square root of n then there won't be.
this means we have to use this only

There may be prime factors greater than the square root..for example take 28. The square root is somewhere between 5 and 6, and the factorization is 2*2*7 - 7 is clearly larger.

But here's what is probably your problem... if you are only checking the primes below the square root, you're checking 2, 3, and 5 - only one of which goes evenly into 28. HOWEVER, what you are missing is that 2 goes in TWICE... so when you divide 28/2, you get 14, which is not prime... but you're never gonna find (28/2)/2 (or 28/4) to get your 7.

I would say you have to check either all the primes less than the number, OR all the numbers below the square root... OR, after you check a prime that divides evenly, check to make sure it doesn't go in again and continue with the quotient each time... although I haven't proved that to myself yet.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

harish thiru
Ranch Hand

Joined: Aug 02, 2008
Posts: 32

posted

0

fred rosenberger

originally posted by fred rosenberger
HOWEVER, what you are missing is that 2 goes in TWICE... so when you divide 28/2, you get 14, which is not prime... but you're never gonna find (28/2)/2 (or 28/4) to get your 7.

i use this know

so i think for 28/2 then still i divide by 2 again so i get to 7 but then i do not consider it 7 as 7>sqrt(7)

originally posted by fred rosenberger
OR, after you check a prime that divides evenly, check to make sure it doesn't go in again and continue with the quotient each time..

to use that condition shouldn't i change the entire for loop code

I think the problem is that you have to test whatever you are left with to see if it's prime. take 66. it factors to 2*3*11. you're only testing up to 9. so you divide by 2, then by 3, and are left with 11. again, i THINK if you check to see if THAT is prime, you're done. If it's not prime, you need to find IT'S factors.

on a different tack... when I did this, I approached it differently. I wrote a method that would reduce an input. So, if you passed it 35, it would return 7. if you passed it 105, it would return 21. if the passed value was not reducible, it was prime.

If you always try and find the smallest factor first, when you're done, you're left with the largest prime factor of the original.

harish thiru
Ranch Hand

Joined: Aug 02, 2008
Posts: 32

posted

0

originally posted by fred rosenberger
If you always try and find the smallest factor first, when you're done, you're left with the largest prime factor of the original.

I don't get this, this is not true always know for example 68 has smallest prime factor has 2 then how are we left with the largest prime factor, unless you mean we start with lowest prime factors then increment and finally the last prime left which after all division is the largest prime factor.

You algorithm is correct - and every thing Jesper Young wrote about prime numbers is correct to!
You end up with a wrong answer for a classic but hard to spot error in your implementation.

The relevant lines ...
for (long i = 2 ; i <= Math.sqrt(N); i++)
.
.
.
N = N/i;

Hope that marks out the mistake clearly for you?

If you are still unclear - here is my next suggestion,
Add the following SOP just below where N = N/i;

The truth is we ended up mixing an algorithm that was for a different purpose with the one you use here.

The algorithm with the less than SQRT(N) is for "Determining if a Number is Prime or not" The logic it work on is pretty simple - if a Number has no factor less than or equal to its sqrt it must be prime."

However this does not mean that a number cannot have one or more prime factors greater than its Sqrt when it is not prime.
So for example, 66 - who sqrt is 9 (between 8 and 9, taking the higher value) has a factor of 2,3, and 11.

In this particular example your algorithm would work since the actual largest prime factor of the number is 6857 which is less the the SQRT of the number 600851475143L. This might not be generally true.

Vlado Zajac
Ranch Hand

Joined: Aug 03, 2004
Posts: 245

posted

0

Jesper Young is right.

But the last (greatest) factor must be handled differently.
Hint: What will be the value of N at the end of the original code?

harish thiru
Ranch Hand

Joined: Aug 02, 2008
Posts: 32

posted

0

This is far efficient than the previous one it reduces so many unwanted iterations, I think this is what you guys meant.
Thanks for all the help

More efficient code or different algorithm or cheekier code please post

On my system comparing i <= n/i is faster than comparing i < Math.sqrt(n).
Also since the number is odd you can initialize i to 3 and inc by 2.

harish thiru
Ranch Hand

Joined: Aug 02, 2008
Posts: 32

posted

0

Yeah even for even numbers i think we should first completely divide by 2, then we could increment by 2, lot of iterations saved.

When i posted solution i found out from project euler overview that

every number n can at most have one prime factor greater than sqrt(N) . If we,
after dividing out some prime factor, calculate the square root of the remaining number we
can use that square root as upper limit for factor. If factor exceeds this square root
we know the remaining number is prime.