Какой самый быстрый метод для проверки на простоту в Java?

Question

Я пытаюсь найти самый быстрый способ проверить, является ли данное число простым или нет (в 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 ");
        }
    }
}

Answer 1

Вот еще один способ:

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's isProbablePrime(...) действительны для всех 32-битных int.

EDIT

Обратите внимание, что isProbablePrime(certainty) не всегда дает правильный ответ. Когда уверенность находится на низкой стороне, она дает ложные срабатывания, как @ dimo414 упомянул в комментариях.

К сожалению, я не смог найти источник, который утверждал, что isProbablePrime(certainty) действителен для всех (32-битных) int (при достаточной уверенности!).

Итак, я выполнил пару тестов. Я создал BitSet размером Integer.MAX_VALUE/2, представляющий все нечетные числа, и использовал простое сито, чтобы найти все простые числа в диапазоне 1..Integer.MAX_VALUE. Затем я зациклился на i=1..Integer.MAX_VALUE, чтобы проверить, что каждые new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == 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 минут.

Answer 2

Это самый элегантный способ:

public static boolean isPrime(int n) {
    return !new String(new char[n]).matches(".?|(..+?)\\1+");
}

Java 1.4+. Импорт не требуется.

Так коротко. Так красиво.

Answer 3

Взгляните на тест простоты AKS (и его различные оптимизации). Это детерминированный тест на простоту, который выполняется за полиномиальное время.

Существует реализация алгоритма на Java из Университета Тюбингена (Германия) здесь

Answer 4

Вы сделали первый шаг в устранении всех кратных 2.

Однако, почему вы остановились там? Вы могли бы удалить все кратные 3, кроме 3, все кратные 5, кроме 5 и т. д.

Когда вы будете следовать этому рассуждению до его завершения, вы получите Сито Эратосфена .

Answer 5

Если вы просто пытаетесь определить, является ли число простым или нет, это достаточно хорошо, но если вы пытаетесь найти все простые числа от 0 до n, лучшим вариантом будет Сито Эратосфена

Но это будет зависеть от ограничений java на размеры массивов и т. Д.

Answer 6

Ваш алгоритм будет хорошо работать для достаточно небольших чисел. Для больших чисел следует использовать продвинутые алгоритмы (например, на основе эллиптических кривых). Другой идеей будет использование некоторого теста «псевдо-простые». Они быстро проверят, что число простое, но они не на 100% точны. Однако они могут помочь вам исключить некоторые числа быстрее, чем с помощью вашего алгоритма.

Наконец, хотя компилятор, вероятно, оптимизирует это для вас, вы должны написать:

int max =  (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}

Answer 7

Быстрый тест, предложенный Jaeschke (1993), является детерминированной версией теста Миллера-Рабина, который не имеет ложных срабатываний ниже 4 759 123 231 и, следовательно, может применяться к Java int s.

// Given a positive number n, find the largest number m such
// that 2^m divides n.
private static int val2(int n) {
  int m = 0;
  if ((n&0xffff) == 0) {
    n >>= 16;
    m += 16;
  }
  if ((n&0xff) == 0) {
    n >>= 8;
    m += 8;
  }
  if ((n&0xf) == 0) {
    n >>= 4;
    m += 4;
  }
  if ((n&0x3) == 0) {
    n >>= 2;
    m += 2;
  }
  if (n > 1) {
    m++
  }
  return m;
}

// For convenience, handle modular exponentiation via BigInteger.
private static int modPow(int base, int exponent, int m) {
  BigInteger bigB = BigInteger.valueOf(base);
  BigInteger bigE = BigInteger.valueOf(exponent);
  BigInteger bigM = BigInteger.valueOf(m);
  BigInteger bigR = bigB.modPow(bigE, bigM);
  return bigR.intValue();
}

// Basic implementation.
private static boolean isStrongProbablePrime(int n, int base) {
  int s = val2(n-1);
  int d = modPow(b, n>>s, n);
  if (d == 1) {
    return true;
  }
  for (int i=1; i < s; i++) {
    if (d+1 == n) {
      return true;
    }
    d = d*d % n;
  }
  return d+1 == n;
}

public static boolean isPrime(int n) {
  if ((n&1) == 0) {
    return n == 2;
  }
  if (n < 9) {
    return n > 1;
  }

  return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
}

Это не работает для long переменных, но другой тест работает: тест BPSW не имеет контрпримеров до 2 ^ 64. Это в основном состоит из 2-сильного вероятного простого теста, подобного описанному выше, за которым следует сильный тест Лукаса, который немного сложнее, но принципиально не отличается.

Оба эти теста намного быстрее, чем любое другое пробное подразделение.

Answer 8

я думаю, что этот метод самый лучший. по крайней мере для меня -

    public static boolean isPrime(int num)
    {
        for (int i = 2; i<= num/i; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }
        return num > 1;
    }

Answer 9

В зависимости от длины числа, которое необходимо проверить, вы можете предварительно вычислить список простых чисел для малых значений (n <10 ^ 6), который используется первым, если запрашиваемое число находится в этом диапазоне. Это конечно самый быстрый способ. Как упоминалось в других ответах, <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer"> Сито Эратосфена является предпочтительным методом для создания такого предварительно вычисленного списка.

Если ваши числа больше этого, вы можете использовать тест Рабина на первичность. Тест Рабина на первичность

Answer 10

То, что вы написали, - это то, что делают большинство обычных программистов и чего должно быть достаточно в большинстве случаев.

Однако, если вы придерживаетесь «лучшего научного алгоритма», есть много вариантов (с разной степенью достоверности), документированных http://en.wikipedia.org/wiki/Prime_number.

Например, если у вас 70-значный номер, физические ограничения JVM могут помешать запуску вашего кода, и в этом случае вы можете использовать «Решета» и т. Д.

Опять же, как я уже сказал, если это был вопрос программирования или общий вопрос использования программного обеспечения, ваш код должен быть идеальным:)