# Smallest prime factor of a large number (using BigInteger)

I'm working on a Project Euler problem and am trying to get the smallest prime factor of a BigInteger:

private static BigInteger smallestPrimeFactor( BigInteger n ){
for( BigInteger i = new BigInteger("2"); n.compareTo(i) >= 0 ; i = i.add(BigInteger.ONE) ){
while( n.mod(i) == BigInteger.ZERO )
return i;
}
}
return BigInteger.ZERO;
}


I have basically just made adjustments to a code snippet I found online. They had something with n = n.divide(i), which I believe was to make things prime, but I wanted to save time just getting the smallest. Is there a better/faster way to go about doing this?

-
@boxed__l it will be prime, because the lowest factor is always prime ... if it was not prime, then the lowest prime-factor of the non-prime value would have been checked already –  rolfl Jan 11 at 3:47
@rolfl Thanks for pointing that out. –  boxed__l Jan 11 at 3:50
@rofl... wow... Thank you! –  Sam Jan 11 at 3:54

This is an interesting requirement, prime-factoring a BigInteger....

First up, though, you should never, never be doing identity comparisons on BigInteger.ZERO:

.... n.mod(i) == BigInteger.ZERO ...


This should be:

n.mod(i).equals(BigInteger.ZERO)


Second, why do you have a while-condition for your exit?

        while( n.mod(i) == BigInteger.ZERO )
return i;
}


That should be an if, surely?

EDIT: You should seriously consider having a pre-calculated set of prime numbers. You can get these lists from many places on the net. This will save a bunch of time. I have found a large number 123456789012345678987654351 which illustrates how slow these algorithms can be....

BigInteger arithmatic is much, much slower than primitive arithmatic. But, you can significantly reduce your BigInteger arithmatic.

Boxed__l is correct about doing 2 as a special-case, and then only checking odd numbers. This will reduce your computations significantly, but, let me suggest another, different approach.

First, if the BigInteger number is smaller than Long.MAX_VALUE there is no reason to use BigInteger. I would recommend that you implement the algorithm multiple ways, one using long, and the other using BigInteger.

Now, I would then have a 'entry' method that looks like:

private static final BigInteger MAXLONG = BigInteger.valueOf(Long.MAX_VALUE);
private static final BigInteger BIGTWO = BigInteger.valueOf(2);

private static BigInteger smallestPrimeFactor( BigInteger n ) {
if (n.compareTo(BigInteger.ONE) <= 0) {
return BigInteger.ZERO;
}
if (n.mod(BIGTWO).equals(BigInteger.ZERO)) {
return BIGTWO;
}
if (n.compareTo(MAXLONG) <= 0) {
// for 'small' n's use a simple long-based prime-factor.
return BigInteger.valueOf(smallestPrimeFactor( n.longValue() ));
}
// use special BigInteger code for this...
return internalPrimeFactor(n);
}


OK, so, what I am saying, is use the fast mechanisms where it is possible. The implementation of the long based solution should be 'trivial'. Use the recommendations others have suggested (treat 2 as a special case, then only work with odd values).

Now, as for your internalPrimeFactor(BigInteger) method, I still recommend you stay in long space as much as you can....

By doing it this way, you will only resrt to slow BigInteger math for large input values, and, even then it will be relatively fast until you get to very large prime numbers....

By my calculations, that will probably take you a couple of days to get to (in order to first search all the prime values less than Long.MAX_VALUE).

Consider the functions:

private static final BigInteger MAXLONG = BigInteger.valueOf(Long.MAX_VALUE);
private static final BigInteger BIGTWO = BigInteger.valueOf(2);

private static BigInteger smallestPrimeFactor( BigInteger n ) {
if (n.compareTo(BigInteger.ONE) <= 0) {
return BigInteger.ZERO;
}
if (n.mod(BIGTWO).equals(BigInteger.ZERO)) {
return BIGTWO;
}
if (n.compareTo(MAXLONG) <= 0) {
// for 'small' n's use a simple long-based prime-factor.
return BigInteger.valueOf(smallestPrimeFactor( n.longValue() ));
}
// use special BigInteger code for this...
return internalPrimeFactor(n);
}

private static final long smallestPrimeFactor(long n) {
if (n < 1) {
return 0;
}
if (n % 2 == 0) {
return 2;
}
// only need aproximate end-point... even if n is larger than 48 bits
// (the largest accurate integer number in double),
// the sqrt will be only off by 1 at most.
long root = (long)(Math.sqrt(n)) + 1;
for (long i = 3; i <= root; i += 2) {
if (n % i == 0) {
return i;
}
}
// it's prime!
return n;
}

/**
* From http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
*/
public static final BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
while(b.compareTo(a) >= 0) {
if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}

private static final BigInteger internalPrimeFactor(BigInteger n) {
// only call this method when n > Long.MAX_VALUE
// See this SO Question: http://stackoverflow.com/a/4407884/1305253
// and using the code from this blog: http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
BigInteger root = sqrt(n);
// keep a limit in long space, swap to BigInteger space when we need to.
long maxlimit = root.compareTo(MAXLONG) > 0 ? Long.MAX_VALUE : root.longValue();
// only need to start from 3, 2 has been dealt with....

for( long i = 3; i <= maxlimit ; i += 2 ){
if( n.mod(BigInteger.valueOf(i)).equals(BigInteger.ZERO) ) {
return BigInteger.valueOf(i);
}
}

// OK, no prime factor found less than Long.
// resort to using BigInteger arithmatic in the loop.
// MAXLONG is odd, we can go from there.
for( BigInteger i = MAXLONG; root.compareTo(i) >= 0 ; i = i.add(BIGTWO)) {
if( n.mod(i).equals(BigInteger.ZERO) ) {
return i;
}
}
// it's prime!
return n;
}


Out of interest, the difference between long-based and BigInteger performance is large. Here are the time differences for a set of calculations where the (long) calculation does (n % i) == 0 and the (BI) calculation does n.mod(BigInteger.valueOf(i).equals(BigInteger.ZERO)

First prime factor of 2305843009213693965 is 3 in 0.000003sec (long) and 0.001277sec (BI)
First prime factor of 2305843009213693967 is 2305843009213693967 in 7.946315sec (long) and 63.071495sec (BI)
First prime factor of 2305843009213693969 is 37 in 0.000005sec (long) and 0.000984sec (BI)
First prime factor of 2305843009213693971 is 3 in 0.000003sec (long) and 0.000978sec (BI)
First prime factor of 2305843009213693973 is 2305843009213693973 in 7.892226sec (long) and 62.610628sec (BI)
First prime factor of 2305843009213693975 is 5 in 0.000005sec (long) and 0.000944sec (BI)
First prime factor of 2305843009213693977 is 3 in 0.000004sec (long) and 0.000913sec (BI)
First prime factor of 2305843009213693979 is 727 in 0.000015sec (long) and 0.000954sec (BI)
First prime factor of 2305843009213693981 is 31 in 0.000004sec (long) and 0.000914sec (BI)
First prime factor of 2305843009213693983 is 3 in 0.000003sec (long) and 0.000876sec (BI)
First prime factor of 2305843009213693985 is 5 in 0.000003sec (long) and 0.000950sec (BI)
First prime factor of 2305843009213693987 is 7014691 in 0.036126sec (long) and 0.313198sec (BI)
First prime factor of 2305843009213693989 is 3 in 0.000007sec (long) and 0.000870sec (BI)
First prime factor of 2305843009213693991 is 41 in 0.000004sec (long) and 0.000836sec (BI)
First prime factor of 2305843009213693993 is 131 in 0.000005sec (long) and 0.000867sec (BI)
First prime factor of 2305843009213693995 is 3 in 0.000003sec (long) and 0.000866sec (BI)
First prime factor of 2305843009213693997 is 128053 in 0.000718sec (long) and 0.006650sec (BI)
First prime factor of 2305843009213693999 is 7 in 0.000017sec (long) and 0.000849sec (BI)
First prime factor of 2305843009213694001 is 3 in 0.000003sec (long) and 0.000845sec (BI)
First prime factor of 2305843009213694003 is 23 in 0.000003sec (long) and 0.000848sec (BI)
First prime factor of 2305843009213694005 is 5 in 0.000002sec (long) and 0.000877sec (BI)
First prime factor of 2305843009213694007 is 3 in 0.000002sec (long) and 0.000862sec (BI)

-

Factors to consider

1. If number 2 is not a factor, then all large even numbers will not be factors. Therefore, checking only the odd numbers is sufficient.

2. For integers i x j = n, if i is larger than the square root of n, then j has to be smaller than the square root of n (Therefore, already checked). Hence, numbers higher than the square root of n do not have to be checked as candidates for prime factors.

private static BigInteger smallestPrimeFactor(BigInteger n) {
BigInteger two = new BigInteger("2");
if (n.mod(two).compareTo(BigInteger.ZERO) == 0) {
return two;
}

for (BigInteger i = new BigInteger("3"); n.compareTo(i.multiply(i)) >= 0; i = i.add(two)) {
if (n.mod(i).compareTo(BigInteger.ZERO) == 0) {
return i;
}
}
return n;
}

-

BigInteger should be compared using compareTo() rather than ==

One optimization would be (search space):

private static BigInteger smallestPrimeFactor( BigInteger n ){
BigInteger two=new BigInteger("2");
if(n.mod(two).compareTo(BigInteger.ZERO)==0){
return two;
}
for( BigInteger i = new BigInteger("3"); n.compareTo(i) >= 0 ; i = i.add(two) ){
if( n.mod(i).compareTo(BigInteger.ZERO)==0)
return i;
}
}
return BigInteger.ZERO;
}

-