# Finding a prime factor

Tom Hong

Greenhorn

Posts: 13

posted 6 years ago

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?

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?

Tom Hong

Greenhorn

Posts: 13

posted 6 years ago

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

84

posted 6 years ago

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:

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Campbell Ritchie

Marshal

Posts: 52580

119

posted 6 years ago

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

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

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

posted 6 years ago

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.

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

119

posted 6 years ago

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

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

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Tom Hong

Greenhorn

Posts: 13

posted 6 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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.

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

Tom Hong

Greenhorn

Posts: 13

posted 6 years ago

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!

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

119

posted 6 years ago

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.

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:

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

posted 6 years ago

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

http://www.coderanch.com/t/516856/java/java/Sieve-Eratosthenes

You can then use these to find you prime factors.

--

Carey

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Campbell Ritchie

Marshal

Posts: 52580

119

posted 6 years ago
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

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

119

posted 6 years ago

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.