• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

project euler

 
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 245
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 32
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Bartender
Posts: 11497
19
Android Google Web Toolkit Mac Eclipse IDE Ubuntu Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This would suit more in the Programming Diversions forum.
Moving.
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 32
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 608
Firefox Browser Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!!
 
Saifuddin Merchant
Ranch Hand
Posts: 608
Firefox Browser Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 245
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 32
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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


 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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
Posts: 32
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


That code will account for even numbers.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic