Project Euler 3: Largest prime factor

Question

How can I improve my code, make it more efficient, and are there any tips you have?

Project Euler 3:

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

What is the largest prime factor of the number 600851475143 ?

public class LargestPrimeFactor {
 public static void main(String[] args) {
 long num = 600851475143L;
 boolean isPrime = true;
 // this is to see if num is factorable
 for (int i = 2; i < num; i++) {
 //if i is a factor, check if its prime
 if (num % i == 0) {
 for (int j = 2; j < i; j++) {
 if (i % j == 0) {
 isPrime = false;
 }
 }
 if (isPrime) {
 System.out.println(i);
 }
 } 
 }
 }
}

• Der Kommissar: I believe int i and int j should be long i and long j respectively. (More than believe, I know it to be true.) You're falling into an integer overflow issue, as the value num is larger than the max value of an int, so, i wraps back around to 0 and throws an exception.
• Phrancis: I ran your code and it printed all the prime factors instead of just the largest one, I also got a divide-by-zero error later because the value of i overflowed the maximum integer. It sounds like the code is not working correctly. Can you please clarify?
• castle-bravo: Your algorithm could be made much more efficient. Here's a hint: if a and b are coprime (that is: a and b have no prime factors in common), but a divides b*c, then a must divide c.
• Martin R: Compare codereview.stackexchange.com/questions/67201/….

Answer 1

A small note first, please do not double-space all lines in code, it just makes it harder to read, rather than easier.

Integer overflow

Using an int primitive type for i and j is causing the number to go through integer overflow and go back to its minimum value -2,147,483,648 (or \$-2^{31}\$), once it exceeds the maximum value 2,147,483,647 (or \2ドル^{31}-1\$), then finally all the way back from there to \0ドル\,ドル resulting in a java.lang.ArithmeticException: divide by zero. To correct this, use a long type for the iterators instead:

 // this is to see if num is factorable
 for (long i = 2; i < num; i++) {
 //if i is a factor, check if its prime
 if (num % i == 0) {
 for (long j = 2; j < i; j++) {

Algorithm

With the above problem fixed, we can now see that the algorithm you use has a few problems. Given the number \$n = 600851475143\$

1. It checks every number \$i\$ in the set \$[2,3,4, \ldots, n-1]\$ to see if it is a factor of \$n\$.

2. For each \$i\,ドル it then checks every number \$j\$ in the set \$[i, i+1, i+2,\ldots, n-2]\$ to see if it is prime.

3. It returns each number that matches both criteria, e.g., 71, 839, 1471 and finally the answer, and then it just keeps on going until \$i = 600851475143 - 1\,ドル which takes a very long time.

The "right" algorithm is very simple, and involves no primality testing. I left an explanation of it in the code comments. This finds the right answer in less than 1 second. There would be other ways to improve it to be more Java/object-oriented, but for the sake of a math exercise like this it should do pretty nicely. Here is a live demo as well.

class LargestPrimeFactor {
 public static void main(String[] args) {
 long N = 600851475143L;
 // First, start from the maximum number and divide by 2
 // until you can no longer divide evenly by 2, i.e., the number is odd
 while (N % 2 == 0) {
 // in the case of 600851475143 this will be skipped entirely since it is an odd number, 
 // but for the sake of generality we will keep it so it can be used on any number
 N /= 2;
 }
 // the next prime number is 3, and all prime numbers from there are odd numbers,
 // so we can safely just add 2 to the factor each time and only test for odd numbers
 // note that this has a small inefficiency in that it will also test for a few non-prime odd numbers
 // like 9, 15, 21, etc. but it's much less computational work to try dividing by a candidate factor than to test for primality.
 for (long factor = 3; factor < N; factor += 2) {
 // if N is evenly divisible by the factor, then we just divide it, and we keep going
 // until N can no longer be divided by a number smaller than itself,
 // in other words, until N is a prime number
 while (N % factor == 0 && factor < N) {
 N /= factor;
 }
 }
 System.out.println("The answer is " + N);
 }
}

• Meni Rosenfeld: This code fails if the largest prime factor is multiple (squared or higher). e.g., if N=25 it will return 1 instead of 5. Changing the condition N%factor==0 to N%factor==0&&factor<N fixes that.
• Phrancis: It's possible that it does @MeniRosenfeld, if that was a bigger program instead of just a PE problem we should definitively think about those special cases
• Meni Rosenfeld: Ok, but keep in mind that a priori we don't know that for this particular PE problem the number is not of this form, so we might as well write a program that is guaranteed to work.
• Phrancis: That's a fair enough critique @MeniRosenfeld and I think maybe you should write an answer about it. In any case though, thank you. Sounds like there should be a "pivot" type of value that changes the way it's handled

Answer 2

 //if i is a factor, check if its prime

It may be pedantic, but "its" should have an apostrophe in it if it is used as a contraction for "it is".

 // if i is a factor, check if it's prime

You are saying "check if it is prime".

More importantly, you don't need to check if the factors are prime if you do it right.

 public static void main(String[] args) {
 long num = 600851475143L;
 long i = 2;
 for ( ; i <= num; i++) {
 //if i is a factor, remove it
 while (num % i == 0) {
 num /= i;
 }
 }
 // the last number must be prime
 System.out.println(i-1);
 }

When this finds a factor, it removes it from num until the new num is no longer divisible by that factor. As a result, if num isn't prime, it's pretty fast. It is (mostly) linear in time relative to the answer.

Note that we can improve things by writing special cases for 2 and 3. Also, the worst behavior occurs when num is prime. If you check for that first, you can limit the worst case to \$O(\sqrt n)\$.

public class Euler3 {
 public long calculateLargestPrimeFactor(long number) {
 long current = 1;
 while (number % 2 == 0) {
 number /= 2;
 current = 2;
 }
 while (number % 3 == 0) {
 number /= 3;
 current = 3;
 }
 if (number == 1) {
 return current;
 }
 current = 5;
 int increment = 4;
 int sqrt_num = (int) Math.sqrt(number);
 for ( ; current <= number; current += increment) {
 if (current > sqrt_num) {
 return number;
 }
 // if current is a factor, remove it
 while (number % current == 0) {
 number /= current;
 }
 increment = 6 - increment;
 }
 // the last number must be prime
 return current - increment;
 }
 public static void main(String[] args) {
 System.out.println(calculateLargestPrimeFactor(600851475149L));
 System.out.println(calculateLargestPrimeFactor(600851475143L));
 System.out.println(calculateLargestPrimeFactor(2 * 600851475149L));
 System.out.println(calculateLargestPrimeFactor(20));
 System.out.println(calculateLargestPrimeFactor(22));
 System.out.println(calculateLargestPrimeFactor(1073741824));
 System.out.println(calculateLargestPrimeFactor(6561));
 }
}

Note that it would be more robust to do the main testing in JUnit or similar.

I also changed the name of i and num to current and number respectively to be clearer.

Answer 3

Performance

You can use a Sieve of Eratosthenes to make it faster.

This is a slightly more complicated sieve as it only sieves the odd numbers up to the square root of the input

public long largestPrimeFactor( final long input ) {
 // Initialise a BitSet for the sieve.
 final BitSet sieve = new BitSet( ((int) Math.sqrt( input )) + 1 );
 // Find if there are factors of 2 and eliminate them.
 long i = Long.numberOfTrailingZeros(input);
 long value = input >> i;
 long maxPrime = i > 0 ? 2 : 1;
 // Loop only over the values which remain in the sieve (i.e. the primes)
 for ( int j = 1; (i = (j<<1)+1) * i <= value; j = sieve.nextClearBit( j + 1 ) ){
 sieve.set(j);
 // Check if it is a factor
 if ( value % i == 0 )
 {
 maxPrime = i;
 // Eliminate the factor
 do value /= i; while( value % i == 0 );
 if ( value == 1 )
 break;
 }
 // Iterate through the sieve setting all the multiples
 // of the current value to be non-prime.
 for ( long k = (i*i-1)>>1; k * k <= value; k += i )
 sieve.set( (int) k);
 }
 return value > 1 ? value : maxPrime;
}

For small numbers, using a simple algorithm will be faster but if you (a) can re-use the sieve when finding/testing multiple numbers or (b) are using it for large numbers; then a sieve is likely to be faster.

• Phrancis: I'm not sure that Sieve of Eratosthenes can solve Project Euler 3 in any reasonable time, I've tried it before and I gave up waiting after it had been computing for over 12 minutes without giving the answer...
• MT0: @Phrancis The code above runs in about the same time (i.e. completes it in ~13μs on my machine) as the accepted answer for Project Euler 3. However, if you modify it so the sieve is a class attribute and maintain the sieve between runs then you start to see significant speed-ups (after initially populating the sieve) and the sieve is about 50% faster (in my tests) than the accepted answer.
• Phrancis: Oh wow, I must have done something really inefficient in my Sieve then, thanks for clarifying!

Answer 4

Efficiency

1. Check only odd numbers
2. Check only numbers to the square root of the number under test
3. You maybe want to count down instead of count up

Robustness

1. You should have a look at BigInteger to avoid overflows and you think about numbers exceeding the Long-Type. This will not be easy.
2. You should not compare Integer-Values with Long-Values as you are using them within the same semantic. Harmonize the algorithm to use only one type for one purpose (in this case Long)

Naming

1. You have algorithms but no names. Break your algorithm in parts and name them meaningfully