programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Finding the largest Prime Factor

Sam Benry
Ranch Hand
Posts: 89
Im trying to solve this problem
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
Marshal
Posts: 55761
163
Welcome to the Ranch.

Please check the JavaRanch naming policy and change your displayed name to conform.

I shall have a look at your code and see whether I can make anything of it. It ought to produce the highest prime factor in a few milliseconds.

Campbell Ritchie
Marshal
Posts: 55761
163
Take a number n.
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

this is taking so long too...
Is this what you want?
by the way, where can I find the naming policy?

Campbell Ritchie
Marshal
Posts: 55761
163
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.

Henry Wong
author
Sheriff
Posts: 23283
125
by the way, where can I find the naming policy?

naming policy

Campbell Ritchie
Marshal
Posts: 55761
163
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.

Garrett Rowe
Ranch Hand
Posts: 1296
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...

Sam Benry
Ranch Hand
Posts: 89
@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

Sam Benry
Ranch Hand
Posts: 89
Fixed the name thing btw

Campbell Ritchie
Marshal
Posts: 55761
163
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
Ranch Hand
Posts: 1296
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
Marshal
Posts: 55761
163
Thank you. How do you do it? I only know how to implement the Sieve of Eratosthenes with an array.

Garrett Rowe
Ranch Hand
Posts: 1296
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 ]

Campbell Ritchie
Marshal
Posts: 55761
163
Thank you, Garrett. I shall have to look at that method later. Does it still require a lot of memory to maintain a collection of prime numbers?

Sam, have you solved the largest prime problem yet?

Garrett Rowe
Ranch Hand
Posts: 1296
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
Marshal
Posts: 55761
163
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?

Sam Benry
Ranch Hand
Posts: 89
I still dont get my errors,
you said
while the remainder is > n

so I wrote

but with this code, the while loop is never executed, but when I change it to

the program starts working...

but it never stops working...
still unable to work it out
here is what im trying

Paul Clapham
Sheriff
Posts: 22507
43
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.

Patrick Loz
Greenhorn
Posts: 5
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
ok solved it, in less than a sec

Campbell Ritchie
Marshal
Posts: 55761
163
Not convinced.

You ought to test while(i < num) and forget about the % operator.

Bill Shirley
Ranch Hand
Posts: 457
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

 It is sorta covered in the JavaRanch Style Guide.