Project Euler Problem #3 in Java - Largest Prime Factor

Question

I have solved the problem and it gives me the right output when the BigInteger has the smaller value, however it kept running for more than 20 minutes with the larger value without printing out an answer. So I'm thinking that there should be a faster algorithm for this program.

The problem states:

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

What is the largest prime factor of the number 600851475143 ?

Main Method:

printPrimeFactors(new BigInteger("13195"));

Output:

29 13 7 5

BUILD SUCCESSFUL (total time: 0 seconds)

But when I change the value:

Main Method

printPrimeFactors(new BigInteger("600851475143"));

The program keeps running for a long time (more than 20 minutes), I didn't wait for an answer and stopped it.

Here is the rest of the program:

public static boolean isPrime(BigInteger n) {
 if(n.compareTo(new BigInteger("2")) == -1) return false;
 if(n.equals(new BigInteger("2")) || n.equals(new BigInteger("3"))) return true;
 if(n.remainder(new BigInteger("2")).equals(BigInteger.ZERO) || n.remainder(new BigInteger("3")).equals(BigInteger.ZERO)) return false;
 BigInteger sqrtN = bigIntSqRootFloor(n).add(BigInteger.ONE);
 for(BigInteger i = new BigInteger("6"); i.compareTo(sqrtN) == 0 || i.compareTo(sqrtN) == -1; i = i.add(new BigInteger("6"))){
 if(n.remainder(i.subtract(BigInteger.ONE)).equals(BigInteger.ZERO)) return false; 
 else if(n.remainder(i.add(BigInteger.ONE)).equals(BigInteger.ZERO)) return false; 
 }
 return true;
}
public static void printPrimeFactors(BigInteger number){
 for(BigInteger i = BigInteger.ZERO.add(number);!i.equals(new BigInteger("1")); i = i.subtract(BigInteger.ONE)){
 if(isPrime(i) && number.remainder(i).equals(BigInteger.ZERO)){
 System.out.print(i + " ");
 number = number.divide(i);
 printPrimeFactors(number);
 break;
 }
 } 
}
public static BigInteger bigIntSqRootFloor(BigInteger x)
 throws IllegalArgumentException { 
 if (x.compareTo(BigInteger.ZERO) < 0) {
 throw new IllegalArgumentException("Negative argument.");
 }
 if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
 return x;
 }
 BigInteger two = BigInteger.valueOf(2L);
 BigInteger y;
 for(y = x.divide(two);
 y.compareTo(x.divide(y)) > 0;
 y = ((x.divide(y)).add(y)).divide(two));
 return y;
} 

Answer 1

First of all, you don't need a BigInteger. The target number fits in a long, use it.

The idea here, of course, is to find the largest prime factor, so given a number \$N\,ドル you should start checking primality starting from \$\lfloor \sqrt{N} \rfloor\$ "downwards." That way, the first prime factor you encounter is the largest one. You can do it like that:

private static final long TARGET_NUMBER = 600851475143L;
public void solve() {
 long start = System.currentTimeMillis();
 final long TARGET_NUMBER_SQRT = (long) Math.sqrt(TARGET_NUMBER);
 for (long factor = TARGET_NUMBER_SQRT; factor > 1L; --factor) {
 if (Utils.isPrime(factor) && (TARGET_NUMBER % factor == 0L)) {
 System.out.println(factor);
 break;
 }
 }
 long end = System.currentTimeMillis();
 System.out.println("Duration: " + (end - start) + " milliseconds.");
}

Above, isPrime is:

public static boolean isPrime(final long candidate) {
 if (candidate < 2L) {
 return false;
 }
 if (candidate % 2 == 0 && candidate != 2L) {
 return false;
 }
 final long candidateSqrt = (long) Math.sqrt(candidate);
 for (long f = 3L; f <= candidateSqrt; f += 2L) {
 if (candidate % f == 0L) {
 return false;
 }
 }
 return true;
}

The performance figures are as follows:

6857
Duration: 303 milliseconds.

• Harout: I didn't realise that it fits in long until it was too late. However I've changed the i form zero to the square root of the number and removed the line where the recursion occurs. It worked like a charm. The duration was less than a second. What a difference! and Thanks for pointing out that I ONLY need the largest prime factor, I guess the answer was in the question the whole time.
• coderodde: @Harout Sure. The answer to each and every PE question is an integer. Yet as far as I recall, you will need BigInteger in later questions.
• mdfst13: The largest prime factor may not be smaller than the square root. Consider 22 for example. Or 23 for that matter.

Answer 2

Counting downwards hurts the performance extremely as you are checking way more values than you have to (e.g. for this value you have to iterate only to the second largest prime number (1471) to know the largest prime number).

final long t0 = System.nanoTime();
final long factor = largestPrimeFactor(600851475143L);
final long t1 = System.nanoTime();
System.out.println(t1 - t0);
System.out.println(factor);

Results (significantly faster):

19071
6857

The code in largestPrimeFactors is a bit modified version of a normal primeFactor method (iterating only over values that are not a multiple of 2 or 3):

public static long largestPrimeFactor(
 final long input) {
 ////
 if (input < 2)
 throw new IllegalArgumentException();
 long n = input;
 long last = 0;
 for (; (n & 1) == 0; n >>= 1)
 last = 2;
 for (; n % 3 == 0; n /= 3)
 last = 3;
 for (long v = 5, add = 2, border = (long) Math.sqrt(n); v <= border; v += add, add ^= 6)
 while (n % v == 0)
 border = (long) Math.sqrt(n /= last = v);
 return n == 1 ? last : n;
}