• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Finding a prime factor

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i don't understand your logic. Can you explain exactly what you're doing?
 
Tom Hong
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Android Opera Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 80266
430
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 80266
430
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks for that bit.
 
fred rosenberger
lowercase baba
Posts: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 13091
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I finally got it! Thanks fred for your wisdom and your help.
 
Campbell Ritchie
Marshal
Posts: 80266
430
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well done Tell us how you managed it.
 
Tom Hong
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 80266
430
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
Two advantages:
  • 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.
     
    Bartender
    Posts: 10982
    87
    Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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: 80266
    430
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Bartender
    Posts: 10982
    87
    Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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: 80266
    430
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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.
     
    You will always be treated with dignity. Now, strip naked, get on the probulator and hold this tiny ad:
    Smokeless wood heat with a rocket mass heater
    https://woodheat.net
    reply
      Bookmark Topic Watch Topic
    • New Topic