Я пытаюсь найти самый быстрый способ проверить, является ли данное число простым или не (в Java). Ниже несколько методов тестирования простоты чисел, которые я придумал. Есть ли какой-либо лучший путь, чем вторая реализация (isPrime2)?
public class Prime {
public static boolean isPrime1(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime2(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
if (n % 2 == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
public class PrimeTest {
public PrimeTest() {
}
@Test
public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
Prime prime = new Prime();
TreeMap<Long, String> methodMap = new TreeMap<Long, String>();
for (Method method : Prime.class.getDeclaredMethods()) {
long startTime = System.currentTimeMillis();
int primeCount = 0;
for (int i = 0; i < 1000000; i++) {
if ((Boolean) method.invoke(prime, i)) {
primeCount++;
}
}
long endTime = System.currentTimeMillis();
Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
methodMap.put(endTime - startTime, method.getName());
}
for (Entry<Long, String> entry : methodMap.entrySet()) {
System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
}
}
}
Другой способ:
boolean isPrime(long n) {
if(n < 2) return false;
if(n == 2 || n == 3) return true;
if(n%2 == 0 || n%3 == 0) return false;
long sqrtN = (long)Math.sqrt(n)+1;
for(long i = 6L; i <= sqrtN; i += 6) {
if(n%(i-1) == 0 || n%(i+1) == 0) return false;
}
return true;
}
и BigInteger isProbablePrime (...)
действителен для всех 32-битных int
.
РЕДАКТИРОВАТЬ
Обратите внимание, что isProbablePrime (уверенность)
не всегда дает правильный ответ. Когда уверенность находится на низком уровне, это дает ложные срабатывания, как @ dimo414 упоминал в комментариях.
К сожалению, мне не удалось найти источник, в котором утверждалось, что isProbablePrime (уверенность)
действительна для всех (32-битных) int
(при условии достаточной уверенности!).
Итак, я провел пару тестов. Я создал BitSet
размера Integer.MAX_VALUE / 2
, представляющий все нечетные числа, и использовал решето простых чисел, чтобы найти все простые числа в диапазоне 1..Integer.MAX_VALUE
]. Затем я зациклился на i = 1..Integer.MAX_VALUE
, чтобы проверить, что каждый новый BigInteger (String.valueOf (i)). IsProbablePrime (sureity) == isPrime (i)
.
Для достоверности 5 и 10, isProbablePrime (...)
давал ложные срабатывания по всей строке. Но с isProbablePrime (15)
ни один тест не прошел.
Вот мой тестовый стенд:
import java.math.BigInteger;
import java.util.BitSet;
public class Main {
static BitSet primes;
static boolean isPrime(int p) {
return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
}
static void generatePrimesUpTo(int n) {
primes = new BitSet(n/2);
for(int i = 0; i < primes.size(); i++) {
primes.set(i, true);
}
primes.set(0, false);
int stop = (int)Math.sqrt(n) + 1;
int percentageDone = 0, previousPercentageDone = 0;
System.out.println("generating primes...");
long start = System.currentTimeMillis();
for(int i = 0; i <= stop; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (stop / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
if(primes.get(i)) {
int number = (i * 2) + 1;
for(int p = number * 2; p < n; p += number) {
if(p < 0) break; // overflow
if(p%2 == 0) continue;
primes.set(p/2, false);
}
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
}
private static void test(final int certainty, final int n) {
int percentageDone = 0, previousPercentageDone = 0;
long start = System.currentTimeMillis();
System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
for(int i = 1; i < n; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (n / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
BigInteger bigInt = new BigInteger(String.valueOf(i));
boolean bigIntSays = bigInt.isProbablePrime(certainty);
if(isPrime(i) != bigIntSays) {
System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
+ bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
" a prime");
return;
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
" minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
}
public static void main(String[] args) {
int certainty = Integer.parseInt(args[0]);
int n = Integer.MAX_VALUE;
generatePrimesUpTo(n);
test(certainty, n);
}
}
, который я запустил, выполнив:
java -Xmx1024m -cp . Main 15
Генерация простых чисел на моей машине заняла ~ 30 секунд. И фактическое испытание всех i
в 1..Integer.MAX_VALUE
заняло около 2 часов 15 минут.
Если вы просто пытаетесь найти, является ли число простым или нет, это достаточно хорошо, но если вы пытаетесь найти все простые числа от 0 до n, лучшим вариантом будет Решето Эратосфена
Но это будет зависеть от ограничений java на размеры массивов и т.д.
Вы сделали первый шаг, исключив все кратные 2.
Однако почему вы остановились на этом? Вы могли бы исключить все кратные 3, кроме 3, все кратные 5, кроме 5, и т. д.
Если следовать этому рассуждению до конца, то получится Решето Эратосфена.
То, что вы написали, - это то, что делают большинство обычных программистов, и этого должно быть достаточно в большинстве случаев.
Однако, если вам нужен "лучший научный алгоритм", существует множество вариантов (с разным уровнем достоверности), задокументированных http://en.wikipedia.org/wiki/Prime_number.
Например, если у вас 70-значное число, физические ограничения JVM могут помешать выполнению вашего кода, в этом случае вы можете использовать "сито" и т.д.
Опять же, как я уже сказал, если бы это был вопрос программирования или общий вопрос использования в программном обеспечении, ваш код должен быть идеальным :)
.В зависимости от длины числа, которое необходимо проверить, вы можете предварительно вычислить список простых чисел для малых значений (n <10 ^ 6), который будет использоваться первым, если запрошенное число находится в этом диапазоне. Это, конечно, самый быстрый способ. Как упоминалось в других ответах, Сито Эратосфена является предпочтительным методом для создания такого предварительно вычисленного списка.
Если ваши числа больше этого, вы можете использовать тест на простоту Рабина. Тест на простоту Рабина
Ваш алгоритм будет хорошо работать для достаточно маленьких чисел. Для больших чисел следует использовать более сложные алгоритмы (основанные, например, на эллиптических кривых). Другой идеей будет использование некоторого теста "pseuso-primes". Они быстро проверят, является ли число простым, но они не являются на 100% точными. Тем не менее, они могут помочь вам исключить некоторые числа быстрее, чем с помощью вашего алгоритма.
Наконец, хотя компилятор, вероятно, оптимизирует это для вас, вы должны написать:
int max = (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}
Взгляните на Тест простоты AKS (и его различные оптимизации). Это детерминированный тест на простоту, который выполняется за полиномиальное время.
Здесь есть реализация алгоритма на Java из Тюбингенского университета (Германия)