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:
• Campbell Ritchie
• Liutauras Vilda
• Tim Cooke
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Devaka Cooray
• Ron McLeod
• paul wheaton
Saloon Keepers:
• Tim Moores
• Piet Souris
• Tim Holloway
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Frits Walraven
• Scott Selikoff

# Finding a prime factor

Greenhorn
Posts: 13
• Number of slices to send:
Optional 'thank-you' note:
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?

lowercase baba
Posts: 13081
67
• Number of slices to send:
Optional 'thank-you' note:
i don't understand your logic. Can you explain exactly what you're doing?

Tom Hong
Greenhorn
Posts: 13
• Number of slices to send:
Optional 'thank-you' note:
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.

Saloon Keeper
Posts: 14488
325
• Number of slices to send:
Optional 'thank-you' note:
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:

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

Marshal
Posts: 76821
366
• Number of slices to send:
Optional 'thank-you' note:

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

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
Marshal
Posts: 76821
366
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
thanks for that bit.

fred rosenberger
lowercase baba
Posts: 13081
67
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 13081
67
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
I finally got it! Thanks fred for your wisdom and your help.

Campbell Ritchie
Marshal
Posts: 76821
366
• Number of slices to send:
Optional 'thank-you' note:
Well done Tell us how you managed it.

Tom Hong
Greenhorn
Posts: 13
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 76821
366
• Number of slices to send:
Optional 'thank-you' note:
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.

Saloon Keeper
Posts: 9714
79
• Number of slices to send:
Optional 'thank-you' note:
For some examples of how to efficiently find a list of primes, see:
https://coderanch.com/t/516856/java/java/Sieve-Eratosthenes

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

Campbell Ritchie
Marshal
Posts: 76821
366
• Number of slices to send:
Optional 'thank-you' note:
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
Saloon Keeper
Posts: 9714
79
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 76821
366
• Number of slices to send:
Optional 'thank-you' note:
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.