Arcane isPrime метод в Java

Ответ 1

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

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). Etc.

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

BTW, не-жадный оператор ? - это то, что заставляет "алгоритм" начинаться с самого короткого и подсчитывать.

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

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

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

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

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

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

Ответ 2

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

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 мс).

Ответ 3

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

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