File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes project euler Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "project euler" Watch "project euler" New topic
Author

project euler

harish thiru
Ranch Hand

Joined: Aug 02, 2008
Posts: 32
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 ?



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
Ranch Hand

Joined: Aug 03, 2004
Posts: 245
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
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


probably i am missing something
Maneesh Godbole
Saloon Keeper

Joined: Jul 26, 2007
Posts: 10451
    
    8

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


[How to ask questions] [Donate a pint, save a life!] [Onff-turn it on!]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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

sorry if i have misunderstood anything
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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


there is no need of any if condition like


could you please post your code
Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 606

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;

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


Cheers - Sam.
Twisters - The new age Java Quiz || My Blog
Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 606

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
Ranch Hand

Joined: Aug 03, 2004
Posts: 245
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


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
Greenhorn

Joined: Nov 02, 2007
Posts: 9


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

Joined: Nov 02, 2007
Posts: 9


That code will account for even numbers.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: project euler