Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Finding a prime factor

Tom Hong
Greenhorn
Posts: 13
I'm trying to figure out what the prime factor of the number 600851475143 (problem #3 on projecteuler http://projecteuler.net/index.php?section=problems&id=3).

The code stops looping at 71 and tells me that the biggest prime factor is 846269833, however this is not the correct. What is the problem with the code here? Also are there any ways to make the code more efficient?

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
i don't understand your logic. Can you explain exactly what you're doing?

Tom Hong
Greenhorn
Posts: 13
I'm first checking to see if a number is indeed a factor of theNumber starting with the highest number that could be a factor. If a number is indeed a factor of theNumber, I'm checking to see if that number is indeed a prime number by dividing it by every number that could potentially be it's factor and seeing if it provides a remainder of 0. As long as the remainder stays a 0, primeCheck stays true. However, a single instance of the remainder not being 0 makes it false and breaks out of that loop. It does this until the first instance of a prime factor, which would be the biggest value prime factor of theNumber.

Stephan van Hulst
Bartender
Posts: 5813
61
Hint: first make a class that is dedicated purely to generating prime numbers. This should make your task a lot more easy. Here's a skeleton you could use:

Michel ten Voorde
Greenhorn
Posts: 26
There are two problems with your code, and one of them is trivial. Hint: line 19.

Furthermore, try to understand what happens inside the if-branch (at line 9). Something is missing.

Campbell Ritchie
Sheriff
Posts: 48981
60
Michel ten Voorde wrote:There are two problems with your code, and one of them is trivial. Hint: line 19. . . .
That is simple to see if we know it, but it is a potentially very serious error.

I have a simple rule of thumb about that sort of error, but I shall keep quiet about it just for now.

Tom Hong
Greenhorn
Posts: 13
Michel ten Voorde wrote:There are two problems with your code, and one of them is trivial. Hint: line 19.

Furthermore, try to understand what happens inside the if-branch (at line 9). Something is missing.

I've fixed the problem at line 19 (doh!). But I can't seem to figure out the problem with the if-branch. I'd appreciate another hint...

Also I want to try redoing this by creating a separate class that finds prime numbers. But first I want to make this one work as long as my logic/code isn't too far off.

Campbell Ritchie
Sheriff
Posts: 48981
60
My rule of thumb is: never say == true or == false or != true or != false.
You don't need to say if (boo == true) . . . You simply say if (boo) . . .
You never need say if (boo == false) . . . but you say if (!boo) . . .

Tom Hong
Greenhorn
Posts: 13
thanks for that bit.

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
there's a great book called "How to Solve It", by George(?) Polya. One of his suggestions is to 'try a simpler case'. I'd try some small numbers, like 6 or 10. I'd also try some numbers that have several prime factors, like 8, 12, or 30.

Stick a bunch of "System.out.println" statements in there, to see what 'guess' becomes each time, and what ranges your loops cover.

I will tell you that I believe your method will not work for 30, but it will work for 35...

Tom Hong
Greenhorn
Posts: 13
thanks to your tips, I realized there are quite a few problems with what I have. I'm gonna try starting over using classes.

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
In Fred Brook's book "The Mythical Man Month", he says you should always plan on building one to throw away. His theory is that your first attempt will always be full of flaws...but you will learn a lot doing it. Hopefully you will agree.

What I found was that your original code would fail for any number that had more than two prime factors. Take 30. You find (in order) it is divisible by 2, 3, and 5. That leaves you 'guesses' of 15, 10, and 6. You then test (one at a time) to see if each of those are prime. None are, so your code fails.

I think your code could be adapted...you've got a lot of the right ideas. You take your starting number, and find the smallest number you can that will divide into it. What you're left with will either be prime, or composite. If it is prime, you know you're done. It would have to be the largest prime factor, since you always factor out the smallest.

If what you are left with is composite (i.e. not prime), then start over, trying to find ITS smallest prime factor.

My solution to this was 40 lines, including 2 lines of comments and 5 blank lines. I also put all my curly braces on lines by themselves, which makes it a longer than it could be.

Tom Hong
Greenhorn
Posts: 13
I finally got it! Thanks fred for your wisdom and your help.

Campbell Ritchie
Sheriff
Posts: 48981
60
Well done Tell us how you managed it.

Tom Hong
Greenhorn
Posts: 13
I don't know if this is the proper way to post this... but here it is
That is the first class to find factors.

This one is to check if they are prime numbers.

And that's the main(?) code.

I've tested it with several different numbers and it seems to work. I also got the correct answer on Project Euler. Still, if there are any improvements that can be made up on it (I'm sure there's a ton), please feel free. I don't know if I've used classes efficiently, so I'd like some comment on that too. Also I got a yellow squiggly under every Vector, stating that it's an Obsolete Collection. When I googled it I realized it has something to do with the fact that Vectors are no longer used. Some explanation on this would be appreciated.

All in all, thanks for the help!

Campbell Ritchie
Sheriff
Posts: 48981
60
In your first class, when you have found one factor, you would do better to divide the number by the factor, and start again from where you got to.
Example: you are trying to factorise 1077232094708723979137 and you find it divides by 7. Divide it by 7 and you get 153890299244103425591, but that itself divides by 7. It's 7 × 7 × 21984328463443346513. I don't know whether that last number is prime; I just hit the number pad until I had a big-looking number!
• 1: it is quicker to divide smaller numbers
• 2: some numbers have the same prime factor several times

• There is no need for anblock. You can writeSimpler, and much better style.

Carey Brown
Ranch Hand
Posts: 1484
18
For some examples of how to efficiently find a list of primes, see:
http://www.coderanch.com/t/516856/java/java/Sieve-Eratosthenes

You can then use these to find you prime factors.
--
Carey

Campbell Ritchie
Sheriff
Posts: 48981
60
Yes, I was thinking you ought to use a sieve of Eratosthenes, which I had forgotten about earlier. But there are some strange examples in that thread. I would suggest you look elsewhere for a sieve algorithm.

Carey Brown
Ranch Hand
Posts: 1484
18
Hmmmmm. I don't know what you mean by "strange". Perhaps they are not for a beginner but towards the end of the thread are some examples of highly optimized code.

Campbell Ritchie
Sheriff
Posts: 48981
60
The optimisations make the code difficult to read or understand. So they are not good examples for beginners. Also I don't believe the saving in memory footprint which the optimisations produce outweighs the increased complexity of the code. I suspect the increased complexity may actually be a slight performance overhead. But I shall leave you to try it.