HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Smallest prime factor of a large number (using BigInteger)

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
smallestnumberlargeusingfactorbigintegerprime

Problem

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?

Solution

Factors to consider

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

-
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;
}

Code Snippets

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;
}

Context

StackExchange Code Review Q#39035, answer score: 4

Revisions (0)

No revisions yet.