Увлёкся недавно простыми числами и мне понадобилась программка для проверки числа на простоту.
Проверяю огромное количество чисел и работаю за пределами long. Первый раз работаю с BigInteger. Поэтому был бы рад услышать мнения по поводу эффективности кода. Можно ли здесь где-нибудь увеличить производительность?
Алгоритм прост:
- проверка равно ли 0,1,2 или меньше ли нуля.
- проверка делится ли без остатка на хотя бы одно нечётное начиная от 3 до квадратного корня самого числа.
Код:
public static boolean isPrime(BigInteger number) {
if (number.compareTo(new BigInteger("0")) < 0)
throw new IllegalArgumentException("The number should be positive");
if (number.toString().equals("1") || number.toString().equals("0"))
return false;
// if the number is even return FALSE, unless the number is "2".
if (isEven(number)) {
if (number.toString().equals("2")) {
return true;
}
return false;
}
long limit = sqrt(number).longValue();
// A loop for searching a divider. If no divider found - return "true".
for (long i = 3; limit >= i; i += 2) {
// if (number % i == 0)
if (number.mod(new BigInteger(String.valueOf(i))).toString().equals("0")) {
// System.out.println("The first divider is " + i);
return false;
}
}
return true;
}
public static boolean isEven(BigInteger number) {
if ((number.and(new BigInteger("1"))).toString().equals("0"))
return true;
else
return false;
}
public static BigInteger sqrt(BigInteger N) {
final BigInteger TWO = new BigInteger("2");
BigInteger result = N.divide(TWO);
while (result.multiply(result).subtract(N).compareTo(BigInteger.ONE.divide(new BigInteger("100000000"))) > 0)
result = result.add(N.divide(result)).divide(TWO);
return result;
}
isProbablePrime()
, а потом проверять каким-нибудь тестом простоты, что это действительно простое число.