Как проверить очень большой BigDecimal на простое число в Java?
В моем программном обеспечении есть следующий код:
boolean isPrime = false;
BigInteger testnumber = new BigInteger(unLikelyPrime.toPlainString());
if (testnumber.isProbablePrime(100))
{
isPrime = true;
}
Тем не менее, некоторые составные числа говорят мне, что они простые.
Примеры:
32589158477649702043=181*12161*14805575143823
198962376391690981640415251545285153602734402721821058212203976095419318882061= 271224769 × 683929111734272089584900601 × 1072582042095206356022742074568536678215669
Какой код Java я мог бы использовать, чтобы получить точный результат: эти примеры являются составными. Есть ли другая библиотека, которую я мог бы использовать. Или кто-нибудь написал тест на простоту, которым они могли бы поделиться?
Любая помощь приветствуется.
РЕДАКТИРОВАТЬ Это больше моего кода:
result.setUnLinkelyPrime(unLikelyPrime.toPlainString());
int trys = 0;
BigInteger testnumber = new BigInteger(unLikelyPrime.toPlainString());
boolean isPrime = false;
for (; trys < 200; trys++)
{
if (testnumber.isProbablePrime(3))
{
if (testnumber.isProbablePrime(40))
{
if (testnumber.isProbablePrime(100))
{
isPrime = true;
break;
}
}
}
unLikelyPrime = unLikelyPrime.add(sievesize);
testnumber = new BigInteger(unLikelyPrime.toPlainString());
}
result.setTrys(trys);
result.setPrime(isPrime);
return result;
Может быть, неправильно складывать тест так, как я?
РЕДАКТИРОВАТЬ Я взял неправильный пример.
Знаете, isProbablePrime(100) — это не «100% уверенность», верно? Кажется наиболее вероятной причиной того, что вы выбрали 100.
@Michael: Это 1-2 ^ -100 уверенности, чего достаточно, чтобы проблема с гораздо большей вероятностью заключалась в ошибке в коде спрашивающего, чем в том, что задавший вопрос фактически трижды достигал 2 ^ -100 вероятности ложноположительного результата.
Я тестирую 200000 номеров и приложение. 100 чисел — это ошибка.
Существует множество алгоритмов проверки простоты. Вы ищете что-то подобное?
Кажется, вы проводите тесты на простоту чисел, отличных от числа, которое вы хотите проверить на простоту, а затем решаете, что исходное число является простым, если какое-либо из этих других чисел является простым. result записывает исходное число, но isPrime устанавливается на основе результатов для этого числа и 199 других.
@ user2357112 Да, ты прав. Это ошибка в моем коде. Большое спасибо.
Почему вы вкладываете isProbablePrime звонки?
@Janez Kuhar, ты тоже прав, такое вложение глупо. Большое спасибо.
Ответы 1
Давайте посмотрим. Простой код вот так
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
class Main {
public static void main(String[] args) {
String text[] = {
"32589158477649702043",
"232862364358497360900063316886467769617",
"198962376391690981640415251545285153602734402721821058212203976095419318882061" };
for (String st : text) {
BigInteger value = new BigInteger(st);
boolean result = value.isProbablePrime(100);
if (result)
System.out.println("Prime");
else
System.out.println("NOT Prime");
}
}
}
Показывает:
NOT Prime
Prime
NOT Prime
Давайте посмотрим на второй пример:
7*1777*26613151*99269775704082066217823753 ==
32862364358497360900063316886467769617 !=
232862364358497360900063316886467769617
Если мы спросим Wolfram Alpha, это гарантирует нам, что второй пример является простым числом.
@user2357112 обнаружил ошибку в моем коде.
Кажется, это скорее ошибка в вашем коде, которую вы нам не показали, чем проблема с
BigDecimal.isProbablePrime.