Метод Arcane isPrime в Java

Во-первых, обратите внимание, что это регулярное выражение применяется к числам, представленным в унарной системе счета, т.е.

1       is 1
11      is 2
111     is 3
1111    is 4
11111   is 5
111111  is 6
1111111 is 7

и так далее. На самом деле можно использовать любой символ (отсюда и . в выражении), но я буду использовать "1".

Во-вторых, обратите внимание, что это регулярное выражение соответствует составным (не простым) числам; таким образом, отрицание обнаруживает первичность.

Пояснение:

Первая половина выражения,

.?

говорит, что строки "" (0) и "1" (1) совпадают, т.е. не простое (по определению, хотя это и спорно.)

Вторая половина на простом английском языке гласит:

Найдите самую короткую строку, длина которой не меньше 2, например, «11» (2). Теперь посмотрим, сможем ли мы сопоставить всю строку, повторив ее. Совпадает ли "1111" (4)? Совпадает ли "111111" (6)? Соответствует ли "11111111" (8)? И так далее. Если нет, попробуйте еще раз для следующей самой короткой строки «111» (3). И Т. Д.

Теперь вы видите, что если исходная строка не может быть сопоставлена ​​как несколько ее подстрок, то по определению она является простой!

Кстати, нежадный оператор ? — это то, что заставляет «алгоритм» начинать с кратчайшего и подсчитывать.

Эффективность:

Это интересно, но определенно неэффективно по разным аргументам, некоторые из которых я приведу ниже:

• Как отмечает @TeddHopp, хорошо известный подход решета Эратосфена не удосужился бы проверить кратные целые числа, такие как 4, 6 и 9, поскольку он уже был «посещен» при проверке кратных 2 и 3. Увы, это регулярное выражение подход исчерпывающе проверяет каждое меньшее целое число.

• Как отмечает @PetarMinchev, мы можем «замкнуть» схему проверки множителей, как только достигнем квадратного корня из числа. Мы должны быть в состоянии, потому что множитель, больше, чем квадратный корень, должен сочетаться с множителем, меньшим, чем квадратный корень (поскольку в противном случае два множителя, большие, чем квадратный корень, дали бы произведение больше, чем число), и если этот больший множитель существует, то мы должны были уже встретить (и, следовательно, сопоставить) меньший множитель.

• Как кратко отмечают @Jesper и @Brian, с неалгоритмической точки зрения рассмотрите, как регулярное выражение должно начинаться с выделения памяти для хранения строки, например, char[9000] для 9000 ... Ну, это было легко, не так ли? ;)

• Как отмечает @Foon, существуют вероятностные методы, которые могут быть более эффективными для больших чисел, хотя они не всегда могут быть правильными (вместо этого появляются псевдопростые числа). Но также существуют детерминированные тесты, которые на 100% точны и намного эффективнее, чем методы на основе сита. Wolfram содержит хорошее резюме.

Унарные характеристики простых чисел и почему это работает, уже были рассмотрены. Итак, вот тест с использованием обычных подходов и этого подхода:

public class Main {

    public static void main(String[] args) {
        long time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeOld(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        time = System.nanoTime();
        for (int i = 2; i < 10000; i++) {
            isPrimeRegex(i);
        }
        time = System.nanoTime() - time;
        System.out.println(time + " ns (" + time / 1000000 + " ms)");
        System.out.println("Done");
    }

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

    public static boolean isPrimeOld(int n) {
        if (n == 2)
            return true;
        if (n < 2)
            return false;
        if ((n & 1) == 0)
            return false;
        int limit = (int) Math.round(Math.sqrt(n));
        for (int i = 3; i <= limit; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}

Этот тест вычисляет, является ли число простым до 9999, начиная с 2. И вот его вывод на относительно мощном сервере:

8537795 ns (8 ms)
30842526146 ns (30842 ms)
Done

Таким образом, это крайне неэффективно, когда числа становятся достаточно большими. (Для до 999 регулярное выражение выполняется примерно за 400 мс.) Для небольших чисел это быстро, но все же быстрее генерировать простые числа до 9999 обычным способом, чем даже генерировать простые числа до 99 старым способом ( 23 мс).

Это не очень эффективный способ проверить, является ли число простым (он проверяет каждый делитель).

Эффективным способом является проверка делителей до sqrt(number). Это если вы хотите быть уверенным, является ли число простым. В противном случае есть вероятностные проверки простоты, которые быстрее, но не на 100% правильны.