project euler

[harish thiru]

the question is project euler 3 one

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

  class Euler03 
{
 public static void main(String[] args)  
    {

 long N = 600851475143l;

 for (long i = 2 ; i <= Math.sqrt(N); i++)
        {

 while (N % i == 0)  
             {

 System.out.println(i);

 N = N/i;
 
              }
         }
    }
}
  

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.

can anyone tell where i have gone wrong

[Vlado Zajac]

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]

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

 for (long i = 2 ; i <= N; i++)    

probably i am missing something

[Maneesh Godbole]

This would suit more in the Programming Diversions forum.
Moving.

[fred rosenberger]

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.

[harish thiru]

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

  while (N % i == 0)     

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

sorry if i have misunderstood anything

[fred rosenberger]

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]

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.

which means i could have done this

  class Euler03 
{

 public static void main(String[] args)  
          {

 long N =600851475143l ;

 long temp=0;

 for (long i = 2 ; i <= N; i++)
             {

 while (N % i == 0)  
                {

 N = N/i;
 
 temp=i; 
 
                }
              }
            
  System.out.println(temp);
           }
}
  

there is no need of any if condition like

 
if(i>temp)
temp=i; 

could you please post your code

[Saifuddin Merchant]

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;

System.out.println("The remainder after division: "+ N);

P.S - I just started on project Euler too. Coincidence - http://java-twisters.blogspot.com/2009/06/puzzle-33-prime-number-optimization.html!

Yippy - This was my 200th post!!

[Saifuddin Merchant]

Sorry. My Bad. What I said above is incorrect.

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]

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]

  
class Euler03   
{  
 public static void main(String[] args)    
    {  
  
 long N = 600851475143l;  
  
 for (long i = 2 ; i <= Math.sqrt(N); i++)  
        {  
  
 while (N % i == 0)    
             {  
   
        N = N/i;  

              }  
         } 

System.out.println("The Largest Prime Factor is: "+ N);  

    }  
}  
  

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

[Brandon Bernie]

long N = 600851475143l;
        for (long i = 3; i <= N/i; i+=2)
            while (N % i == 0)
                N = N / i;
        System.out.println(N);

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]

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.

This is what anyway you guys were telling me

[Brandon Bernie]

long k = 600851475143L;

if ((k & 1) == 0) 
    while (k % 2 == 0) 
        k = k / 2;
 
for (int j = 3; j <= k/j; j+=2) 
    while (k % j == 0) 
        k = k / j;         

System.out.println(k);

That code will account for even numbers.