This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
What is i/2lem? I think you misunderstood the advice. The factors of a number can surely exceed the square root of the number. Take 24 for example. 12 is a factor, and is bigger than the square root of 24. However, let's say you have a number n that can be factored into j * k, where j <= k. Then j <= sqrt(n). So, if you're trying to find the prime factors of n, you can iterate through prime numbers up to sqrt(n). If you find a prime factor, divide n by that number and keep going.
I love the Euler problems. They really get you thinking.
Also, what is prime.isPriime() doing? It might be running through a loop just like this one, which makes the workload that much more enormous. I'd forget that part. Unless you have a list of primes to check against, just see if your i is a factor of n. If you keep dividing n by i as you find factors, then all the factors you find will be prime, even if try out many non-prime i candidates. Whatever n ends up as when n / i < i is your answer.
Randall Twede wrote:
i just dont get it...why does it work fine with 100, bot not with 600851475143L is it because of the L?
No, it's not because of the L. All that does is tell the compiler "Treat this value as a long instead of an int."
It appears to be what people have been telling you all along: It's taking longer than you're waiting.
Your solve() method is O(n^2).
So 200 will take 4 times as long as 100.
300 will take 9 times as long as 100.
1,000 will take 100 times as long as 100.
And, since is 600851475143L is about 6008514751 times as big as 100, it will take 6008514751^2 = 36,102,249,512,984,592,001 times as long as 100.
So if 100 takes 1 ns, you should expect 600851475143L to take about 1144 years.
Randall Twede wrote:i haven't tried it yet, but i have a gut feeling you gave me the answer
it still looks wrong to me though.we are back to sqrt(i) instead of i/2
Maybe I'm not understanding your problem correctly, but if you're looking for the factors of i, they will all be covered by the time you get to sqrt(i). Are you still doubting that? If so, I don't know how else to explain it to you. Did you see my "diagram" several posts ago?
Jeff Verdegan wrote:lets you stick with integer math.
At least until the numbers get big and integers overflow.
That's when I would switch to BigInteger. Since we're doing integer math, I prefer to stick to integers, mostly as a matter of principle, but also because I don't want to take the chance of FP error messing up my calculations. I don't know if it would come into play in this situation, but since double cannot represent every long value, I don't want to take the chance.
Pat Farrell wrote:Floating point has no value in any factoring code. You have to use integer, bigint, etc.
for 99% of what we programmers write, Floating Point is evil.
Sorry I mis-read your previous post. For some reason I thought you were suggesting using x < sqrt(i) instead of x * x < i. Didn't realize you were talking about something completely different. I don't know where my head was.
Randall Twede wrote:so....any suggestions?
even O(log n) sounds better
i know this can be solved because many people have done it before
Yes, it can be done. My solution (in Scala) just takes a fraction of a second to solve this. But the fun in these problems is thinking about it and finding a solution yourself, so I'm not sure how much I should give away.
With regard to this problem, it's good to keep the fundamental theorem of arithmetic in mind: any integer greater than 1 can be written as a unique product of primes ("unique" means: each number can be factored in exactly one way into prime factors, and no other number has the same set of prime factors).
Consider a composite (non-prime) number N that has just two prime factors p1 and p2, so that N = p1 * p2. It's easy to see that either p1 or p2 (or both) must be smaller than sqrt(N). Think of squares and rectangles: you can have a square, for example N = 25 = 5 * 5. In that case both p1 and p2 are sqrt(25) = 5. You can also have a rectangle, for example N = 21 = 3 * 7. In such a rectangular number you have a short and a long side and the short side is always < sqrt(N).
If you think about composite numbers with 3 prime factors, for example N = p1 * p2 * p3 etc., you can extend the idea of the square to a cube. At least one of the primes must be < N^(1/3) (the cube root of N). The cube root is always smaller than the square root. So for any composite number (with any number of prime factors) the square root is always a safe limit.
So to find a prime factor you only need to check up to sqrt(N). If you don't find a prime factor, then you know that N is a prime itself.
Note that checking up to the square root instead of the number itself makes a huge difference. Checking all numbers from 2 to 600,851,475,143 takes a very long time. But the sqrt of 600,851,475,143 is only about 775,146, a much smaller number.
Now, suppose that you've found a prime factor p1 of N, so you know N = p1 * N'. To find another prime factor, you can just divide N by p1: N' = N / p1 and find a prime factor of N'. And so on, until you end up with a number that is itself prime: N = p1 * N' = p1 * p2 * N'' = p1 * p2 * p3 * N''' ... That way you can find all the prime factors of N in a fairly efficient way: each time you find a prime factor, you can divide it out, and all you have to do to find the next one is factor a smaller number.
i am still having trouble seeing it. but i am doing no good with my current approach. 7 is a prime factor of 14. how do you find that if you only go to sqrt 14?
here is my latest effort. it is slightly better(because the first prime factor it finds is the answer) but still takes too long.
i will try to figure this out thanks to you all. especially Jesper who must think he is talking to a stump
i think i get it now. the remainer is the last factor and also the answer. if there is a factor bigger than sqrt(i) it will be the remainder
i should probably try something like this
if there is a factor