This week's book giveaway is in the Android forum. We're giving away four copies of Head First Android and have Dawn & David Griffiths on-line! See this thread for details.

this is messed up. someone told me the factors of i dont exceed Math.sqrl(i)
that is wrong the factors can go up to i/2
now i have a problem
here is the code

this works but when i use the real number(600851475143), it hangs up

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.

Randall Twede wrote:i dont understand why the program works when given 100 but hangs up when given that long number

if enough time is over 5 minutes you are right

I would guess it's more like months, or perhaps geological eons. But stick some debugging code in there which shows you where it's up to with its dividing to get a better feel for that.

Randall Twede wrote:this is messed up. someone told me the factors of i dont exceed Math.sqrl(i)

That's not what I said.

I said when finding the factors--such as testing for primeness--you don't need to go beyond sqrt(i). And that statement was correct.

Once you hit 6, you don't need to look any further, because everything beyond that has already been found as the matching factor of the one you're testing.

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?
[/code]

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.

O(n^2) algorithms always become impossible for big N. The answer is "don't do that"

Find a better algorithm.

Factoring numbers is a well explored field, the crypto folks do it all the time. Google for a better approach. The naive ones always start as O(n^2) and some are O(n^4)

That something works for 10 and is OK for 100 and dies for a big number menas you are doing it wrong.

1) When looking for factors, use i * i < target as your loop condition, rather than i < target / 2. This will make your outer loop O(sqrt(n)) instead of O(n), making your overall performance O(n^1.5).

2) Make sure your isPrime() method isn't itself O(n^2).

3) As suggested, print out progress marks and timestamps. For instance, every 1,000,000, or every time you reach the next biggest factor of 10. This way you can get a feel for how it's progressing.

4) Search the web for other implementations and compare their approaches to yours.

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
but i try it. you sound like you have already done it

Jeff Verdegan wrote:lets you stick with integer math.

At least until the numbers get big and integers overflow.

With disk drives so big and cheap, you could calculate the factors of all of the integers and just store them. So with some setup, you have an O(1) solution

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

Randall Twede wrote: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?

Because you'll hit 2 before you get to sqrt(14), and when you hit 2, you'll find that 14 / 2 = 7. Now we've got factors 2 and 7.

This is the same thing I said in my first reply here, where I used the factors of 36 as an example.

me wrote:

Once you hit 6, you don't need to look any further, because everything beyond that has already been found as the matching factor of the one you're testing.

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
getFactor(bigAssNumber)
if there is a factor
getFactor(bigAssNumber/theLastFactor)

Randall Twede wrote: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

Eh? Remainder?

If A*B = C, then C/A = B and C/B = A, and since A and B are factors of C, there's no remainder in either case. By definition