Project Euler Problem #3 in Java - Largest Prime Factor 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) &amp;&amp; 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) &lt; 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)) &gt; 0;
            y = ((x.divide(y)).add(y)).divide(two));
    return y;
}
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 &lt; 2)
        throw new IllegalArgumentException();

    long n = input;
    long last = 0;
    for (; (n &amp; 1) == 0; n &gt;&gt;= 1)
        last = 2;
    for (; n % 3 == 0; n /= 3)
        last = 3;
    for (long v = 5, add = 2, border = (long) Math.sqrt(n); v &lt;= border; v += add, add ^= 6)
        while (n % v == 0)
            border = (long) Math.sqrt(n /= last = v);
    return n == 1 ? last : n;
}