# Finding the largest Prime Factor

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

Im trying to solve this problem

My code is this:

I think this code will work but it will take FOREVER to work, I waited about an hour and got no results...

anyone have any alternative code or any idea to get the right answer?

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My code is this:

I think this code will work but it will take FOREVER to work, I waited about an hour and got no results...

anyone have any alternative code or any idea to get the right answer?

Campbell Ritchie

Sheriff

Posts: 50702

83

Campbell Ritchie

Sheriff

Posts: 50702

83

posted 8 years ago

Take a number n.

Start with n = 2.

while the remainder is > n

if the number divides exactly by n

divide the number by n

else

increase n by 1

end while

print result

The problem you have is that you are repeatedly checking whether the number is prime, and also counting donw; it creates exponential complexity. Once you get above maybe 20 digits, factorisation always becomes a very slow process.

Start with n = 2.

while the remainder is > n

if the number divides exactly by n

divide the number by n

else

increase n by 1

end while

print result

The problem you have is that you are repeatedly checking whether the number is prime, and also counting donw; it creates exponential complexity. Once you get above maybe 20 digits, factorisation always becomes a very slow process.

Sam Benry

Ranch Hand

Posts: 89

Campbell Ritchie

Sheriff

Posts: 50702

83

posted 8 years ago

Since the number is less than 19 digits long, I tried it with longs rather than BigIntegers. It found the largest prime factor (at least I think it did) in <1 second. Try changing to long. Remember that any factorisation algorithm is prone to exponential complexity and the time to solve it increases proportionally to 2^n where n is how many digits the number has.

The naming policy is explained here.

The naming policy is explained here.

Campbell Ritchie

Sheriff

Posts: 50702

83

posted 8 years ago

The problem is the condition for the while loop. There is a subtle mistake in that line which converts the condition to a tautology. I copied and pasted your code, corrected the error and added some calls to System.currentTimeMillis(). It took 37 ms.

Changing your number to 132456600851475143 lengthened the running time to 6.5 seconds, and changing to 1324567600851475143 made it take over � hour and I stopped it with ctrl-C. I told you it would take much longer if you lengthen the number; there was an article in Scientific American either this month or last month about quantum computing. Read that; it says more about how long it can take to factorise big numbers.

I shall leave you to find the error; read the line starting which very carefully. I think there are two things you have to alter. If you can't find it by tomorrow I shall try some hints. Good luck.

Changing your number to 132456600851475143 lengthened the running time to 6.5 seconds, and changing to 1324567600851475143 made it take over � hour and I stopped it with ctrl-C. I told you it would take much longer if you lengthen the number; there was an article in Scientific American either this month or last month about quantum computing. Read that; it says more about how long it can take to factorise big numbers.

I shall leave you to find the error; read the line starting which very carefully. I think there are two things you have to alter. If you can't find it by tomorrow I shall try some hints. Good luck.

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago

This problem comes from Project Euler a pretty cool site. I only know because I just solved it about a week ago. One thing you should know is that Project Euler problems build upon themselves, so once you get to Problem 7 and especially Problem 10, even the solution you have now is going to take a good bit of time. My suggestion would be to read to google "sieve of eratosthenes", you'll find a useful algorithm for for building a list of prime numbers. Good luck.

FWIW, I'm currently stuck trying to figure out an algorithm for Problem 18. I think I'll be starting a topic in the Programming Diversions forum soliciting a little help...

FWIW, I'm currently stuck trying to figure out an algorithm for Problem 18. I think I'll be starting a topic in the Programming Diversions forum soliciting a little help...

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

@Campbell Ritchie

gives me The literal 600851475143 of type int is out of range...

@Garrett Rowe, I solved problems 7 and 10 long time ago, i just cant seem to solve this one :S

@Campbell Ritchie, are you talking about the first code or the second code, and could you please hint or give me more explanation about the error I made? please...

thanks all

gives me The literal 600851475143 of type int is out of range...

@Garrett Rowe, I solved problems 7 and 10 long time ago, i just cant seem to solve this one :S

@Campbell Ritchie, are you talking about the first code or the second code, and could you please hint or give me more explanation about the error I made? please...

thanks all

Campbell Ritchie

Sheriff

Posts: 50702

83

posted 8 years ago

Thank you for correcting your name.

Garrett Rowe is right that I have provided a very simple solution; the sieve of Eratosthenes will provide a list of prime numbers starting from 2.

Unfortunately if you are factorising an 18-digit number you might in theory have a factor which has 9 digits in; you would require an array with 1000000000 members to represent all 9-or-fewer-digit numbers and you are risking running out of memory.

As I said, all factorising solutions run the risk of going into exponential complexity, so they tend to take ages to run. Once you get beyond 50 digits in decimal you are liable to find a program might take millions of years to produce a result. You can improve the algorithm by stopping divisions when you reach the square root of the original number; if you haven't found the largest prime factor by then, whatever remains is the answer.

Try changing "long a = 600851475143;" to "long a = 600851475143L;" If you miss the L out you are implying that the number literal is an int, which can't take 12 digits.

I was talking about the 2nd lot of code; there are two significant errors, both in the condition for the while loop.You are testing the remainder (what in contintental Europe they call modulus). You are testing whether it is smaller, whereas you actually want to test for being larger. If you correct both those errors your app should run nicely.

Garrett Rowe is right that I have provided a very simple solution; the sieve of Eratosthenes will provide a list of prime numbers starting from 2.

Unfortunately if you are factorising an 18-digit number you might in theory have a factor which has 9 digits in; you would require an array with 1000000000 members to represent all 9-or-fewer-digit numbers and you are risking running out of memory.

As I said, all factorising solutions run the risk of going into exponential complexity, so they tend to take ages to run. Once you get beyond 50 digits in decimal you are liable to find a program might take millions of years to produce a result. You can improve the algorithm by stopping divisions when you reach the square root of the original number; if you haven't found the largest prime factor by then, whatever remains is the answer.

Try changing "long a = 600851475143;" to "long a = 600851475143L;" If you miss the L out you are implying that the number literal is an int, which can't take 12 digits.

I was talking about the 2nd lot of code; there are two significant errors, both in the condition for the while loop.

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago

Actually that depends on your implementation strategy. You don't
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

**Campbell: Unfortunately if you are factorising an 18-digit number you might in theory have a factor which has 9 digits in; you would require an array with 1000000000 members to represent all 9-or-fewer-digit numbers and you are risking running out of memory.**

Actually that depends on your implementation strategy. You don't

*need*to use an array at all.

Campbell Ritchie

Sheriff

Posts: 50702

83

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Here's an implementation that doesn't use an array. Instead it stores the next few non-prime numbers in a Map, if the number isn't in the Map, when the sieve "gets to it" then the number is prime.

To be fair to your earlier comment, you aren't likely to generate any nine digit primes with this sieve either. It slows waaaay down after about the 250,000th prime.

\

[ March 22, 2008: Message edited by: Garrett Rowe ]

To be fair to your earlier comment, you aren't likely to generate any nine digit primes with this sieve either. It slows waaaay down after about the 250,000th prime.

\

[ March 22, 2008: Message edited by: Garrett Rowe ]

Campbell Ritchie

Sheriff

Posts: 50702

83

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago

The class doesn't really maintain a collection of primes, it actually maintains a collection of the next few non primes, and generates the next prime based on the next number that's not in the collection. That being said, as numbers get larger the distance between primes gets larger and therefore there are more non primes maintained in the Map. I haven't profiled it, but I would guess its pretty inefficient for very large numbers.
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Originally posted by Campbell Ritchie:

Does it still require a lot of memory to maintain a collection of prime numbers?

The class doesn't really maintain a collection of primes, it actually maintains a collection of the next few non primes, and generates the next prime based on the next number that's not in the collection. That being said, as numbers get larger the distance between primes gets larger and therefore there are more non primes maintained in the Map. I haven't profiled it, but I would guess its pretty inefficient for very large numbers.

Campbell Ritchie

Sheriff

Posts: 50702

83

posted 8 years ago

Yes, I can more-or-less see how it works. It would work well for a single run where you are trying to factorise a single number, but for repeated runs an array would be more economical on time albeit expensive on memory.

And of course you can get all the primes under 1000000 for 1000 passes through an array; you only have to go as far as the square root of the largest number.

And Sam, have you got the algorithm to work?

And of course you can get all the primes under 1000000 for 1000 passes through an array; you only have to go as far as the square root of the largest number.

And Sam, have you got the algorithm to work?

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

That's because "num % i" always returns a number between 0 and i-1. So "num % i < i" is always going to be true. So your loop never ends.

Therefore, that isn't the correct stopping condition. If you explain the algorithm to yourself out loud, you should be able to figure out what the correct condition is.

Therefore, that isn't the correct stopping condition. If you explain the algorithm to yourself out loud, you should be able to figure out what the correct condition is.

Patrick Loz

Greenhorn

Posts: 5

posted 8 years ago

Awesome site! The first I've seen of it... Tons of fun problems...

Originally posted by Garrett Rowe:

This problem comes from Project Euler a pretty cool site. I only know because I just solved it about a week ago. One thing you should know is that Project Euler problems build upon themselves, so once you get to Problem 7 and especially Problem 10, even the solution you have now is going to take a good bit of time. My suggestion would be to read to google "sieve of eratosthenes", you'll find a useful algorithm for for building a list of prime numbers. Good luck.

FWIW, I'm currently stuck trying to figure out an algorithm for Problem 18. I think I'll be starting a topic in the Programming Diversions forum soliciting a little help...

Awesome site! The first I've seen of it... Tons of fun problems...

Sam Benry

Ranch Hand

Posts: 89

Campbell Ritchie

Sheriff

Posts: 50702

83

Bill Shirley

Ranch Hand

Posts: 457

posted 8 years ago

The fact that prime factorization blows up is what makes public key encryption so secure. You take two huge prime numbers (easy to find a prime), multiply them (easy), and provide the larger number publicly (factoring it is not feasible).

details slightly more complicated,

wikipedia.org - RSA

details slightly more complicated,

wikipedia.org - RSA

Bill Shirley - bshirley - frazerbilt.com

if (Posts < 30) you.read( JavaRanchFAQ);