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:
• Tim Cooke
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Liutauras Vilda
Sheriffs:
• Rob Spoor
• Junilu Lacar
• paul wheaton
Saloon Keepers:
• Stephan van Hulst
• Tim Moores
• Tim Holloway
• Carey Brown
• Scott Selikoff
Bartenders:
• Piet Souris
• Jj Roberts
• fred rosenberger

# factors: i hate math

Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Sheriff
Posts: 3036
12
• Number of slices to send:
Optional 'thank-you' note:
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
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
maybe i need to post more code

Sheriff
Posts: 27235
87
• Number of slices to send:
Optional 'thank-you' note:
And it probably isn't hanging, you just haven't given it enough time to do all the calculations.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Greg Charles
Sheriff
Posts: 3036
12
• Number of slices to send:
Optional 'thank-you' note:
You could print out i if you really think it's hanging. I think you'd see that i would keep going up, but you've given it a lot of i's to run through.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Paul Clapham
Sheriff
Posts: 27235
87
• Number of slices to send:
Optional 'thank-you' note:

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
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Greg Charles
Sheriff
Posts: 3036
12
• Number of slices to send:
Optional 'thank-you' note:
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.

Paul Clapham
Sheriff
Posts: 27235
87
• Number of slices to send:
Optional 'thank-you' note:
Yes, the smallest divisor of a number (other than 1 of course) must always be a prime.

(Proof left as an exercise for students who don't hate math.)

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:

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

Paul Clapham
Sheriff
Posts: 27235
87
• Number of slices to send:
Optional 'thank-you' note:
It probably does work fine with the big number. You just have to wait for it to finish.

However you seem to have implemented one of the slowest possible ways of finding the answer, so you might have to wait quite a long time.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

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
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
so....any suggestions?
even O(log n) sounds better
i know this can be solved because many people have done it before

Rancher
Posts: 4686
7
• Number of slices to send:
Optional 'thank-you' note:
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.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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"

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:

use i < target

that is kind of funny because that is where i started
i need to think about what you said though
thanks

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
my original code said while <= Math.sqrt(i)

this worked quickly but gave wrong answer

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
stuck in a love/hate relationship

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

Randall Twede wrote:

use i < target

that is kind of funny because that is where i started
i need to think about what you said though
thanks

That's not what I said.

I said use i * i < target . This is equivalent to i < Math.sqrt(target) but lets you stick with integer math.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Pat Farrell
Rancher
Posts: 4686
7
• Number of slices to send:
Optional 'thank-you' note:

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

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Pat Farrell
Rancher
Posts: 4686
7
• Number of slices to send:
Optional 'thank-you' note:
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.

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Java Cowboy
Posts: 16084
88
• Number of slices to send:
Optional 'thank-you' note:

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.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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.

Randall Twede
Ranch Hand
Posts: 4716
9
• Number of slices to send:
Optional 'thank-you' note:
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)

Jeff Verdegan
Bartender
Posts: 6109
6
• Number of slices to send:
Optional 'thank-you' note:

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

Jesper de Jong
Java Cowboy
Posts: 16084
88
• Number of slices to send:
Optional 'thank-you' note:

Randall Twede wrote:i should probably try something like this
getFactor(bigAssNumber)
if there is a factor
getFactor(bigAssNumber/theLastFactor)

Yes, that's correct!

 pie. tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton