Finding the largest Prime Factor

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?

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.

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.

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

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.

by the way, where can I find the naming policy?

naming policy

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.

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

@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

Fixed the name thing btw

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.

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.

Thank you. How do you do it? I only know how to implement the Sieve of Eratosthenes with an array.

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.

import java.util.Map;
import java.util.Set;
import java.util.Arrays;
import java.util.HashSet;
import java.util.HashMap;
 
/**
* A java implentation of a Sieve of Eratosthenes inspired by
* the Haskell implementation discussed in "The Genuine Sieve of Eratosthenes"
* by Melissa E. O'Neil. That paper can be found at
* <a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf" target="_blank" rel="nofollow">http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf</a>
*/
public class Sieve
{
   private Map<Integer, Set<Integer>> notPrimes;
   int currentPrime;
 
   /**
   * Creates a new Sieve object.
   */
   public Sieve()
   {
      notPrimes = new HashMap<Integer, Set<Integer>>();
      currentPrime = 1;
   }
 
 
   /**
   * Returns the next prime number in the Sieve.
   */
   public int nextPrime()
   {
      currentPrime++;
 
      
      //Keep incrementing currentPrime until we find a value that is not
      //in the notPrimes map.
      while (notPrimes.containsKey(currentPrime))
      {
         Set<Integer> factors = notPrimes.remove(currentPrime);
         for (Integer e : factors)
         {
            updateMap(e + currentPrime, e);
         }
         currentPrime++;
      }
      
      //Small optimization discussed in the referenced paper. 
      //We can start "marking off" nonprimes starting with n^2
      //because all other multiples of n < n^2 will have been 
      //"marked off" by other numbers.
      updateMap(currentPrime * currentPrime, currentPrime);
 
      return currentPrime;
   }
 
   private void updateMap(Integer newKey, Integer newValue)
   {
      if (notPrimes.containsKey(newKey))
      {
         Set<Integer> vals = notPrimes.get(newKey);
         vals.add(newValue);
         notPrimes.put(newKey, vals);
      }
 
      else
      {
         notPrimes.put(newKey, new HashSet<Integer>(Arrays.asList(newValue)));
      }
   }
}

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 ]

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?

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.

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?

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

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.

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

ok solved it, in less than a sec

thanks everybody for your help

Not convinced.

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

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