# factors: i hate math

posted 4 years ago

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

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

SCJP

Visit my download page

posted 4 years ago

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.

I love the Euler problems. They really get you thinking.

posted 4 years ago

that was a typo sorry. 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

man: this sucks i am sorry the code should have been i/2 or something.the forum didnt list when i said that

if enough time is over 5 minutes you are right

man: this sucks i am sorry the code should have been i/2 or something.the forum didnt list when i said that

SCJP

Visit my download page

posted 4 years ago

no it is not. when i use 1oo, the output is perfect

when i use that big number i i get a very short list of factors. the smallest is 71

when i use that big number i i get a very short list of factors. the smallest is 71

SCJP

Visit my download page

posted 4 years ago

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

posted 4 years ago

thats what i di by replacing 600851475143L with 100. it didnt work, but using 100 it did

i think it is a syntax type problem

i think it is a syntax type problem

SCJP

Visit my download page

posted 4 years ago

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.

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.

posted 4 years ago

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.

posted 4 years ago

i just dont get it...why does it work fine with 100, bot not with 600851475143L is it because of the L?

i just dont get it...why does it work fine with 100, bot not with 600851475143L is it because of the L?

SCJP

Visit my download page

posted 4 years ago

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

posted 4 years ago

so....any suggestions?

even O(log n) sounds better

i know this can be solved because many people have done it before

even O(log n) sounds better

i know this can be solved because many people have done it before

SCJP

Visit my download page

posted 4 years ago

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.

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.

posted 4 years ago

1) When looking for factors, use

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.

Randall Twede wrote:so....any suggestions?

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.

posted 4 years ago

well at least i was only n^2

you are all probably right if i google enough i will probably find something.

i was worried the program was "hung up"

you are all probably right if i google enough i will probably find something.

i was worried the program was "hung up"

SCJP

Visit my download page

posted 4 years ago

that is kind of funny because that is where i started

i need to think about what you said though

thanks

use i < target

that is kind of funny because that is where i started

i need to think about what you said though

thanks

SCJP

Visit my download page

posted 4 years ago

my original code said while <= Math.sqrt(i)

this worked quickly but gave wrong answer

this worked quickly but gave wrong answer

SCJP

Visit my download page

posted 4 years ago

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

either that or i just say to hell with it

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

either that or i just say to hell with it

SCJP

Visit my download page

posted 4 years ago

Maybe I'm not understanding your problem correctly, but if you're looking for the factors of i, they will

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?

posted 4 years ago

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

posted 4 years ago

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.

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.

posted 4 years ago

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.

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.

posted 4 years ago

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

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

SCJP

Visit my download page

posted 4 years ago

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.

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.

posted 4 years ago

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)

i should probably try something like this

getFactor(bigAssNumber)

if there is a factor

getFactor(bigAssNumber/theLastFactor)

SCJP

Visit my download page

posted 4 years ago

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

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