patternjavaMinor
Smallest prime factor of a large number (using BigInteger)
Viewed 0 times
smallestnumberlargeusingfactorbigintegerprime
Problem
I'm working on a Project Euler problem and am trying to get the smallest prime factor of a
I have basically just made adjustments to a code snippet I found online. They had something with
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
-
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.