Вопрос с интервью: каков самый быстрый способ рекурсивно генерировать простое число?

Генерация простого числа проста, но самый быстрый способ найти его и сгенерировать (простые числа) рекурсивно?

Вот мое решение. Однако это не лучший способ. Я думаю, что это O (N * sqrt (N)). Пожалуйста, поправьте меня, если я ошибаюсь.

    public static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        } else if (n % 2 == 0 & n != 2) {
            return false;
        } else {
            return isPrime(n, (int) Math.sqrt(n));
        }
    }

    private static boolean isPrime(int n, int i) {
        if (i < 2) {
            return true;
        } else if (n % i == 0) {
            return false;
        } else {
            return isPrime(n, --i);
        }
    }

   public static void generatePrimes(int n){
       if(n < 2) {
            return ;
       } else if(isPrime(n)) {
            System.out.println(n);
       } 

       generatePrimes(--n);

   }

   public static void main(String[] args) {

        generatePrimes(200);
   }

Ответ 1

Для рекурсии вы должны использовать memoization, чтобы улучшить вашу рекурсивную функцию, означает, что если вы найдете простое число, сохраните его в массиве и при вызове isPrime(n) сначала проверьте, существует ли число в массиве, если не вызов isPrime (n, (int) Math.sqrt(n)). также, если isPrime (n, i) возвращает true, добавляет его в первичный список, лучше сортирует ваш массив для выполнения двоичного поиска, на С# - отсортированный список и операция двоичного поиска [создание списка элементов n принимает O (n log n), а поиск - O (log (n))] Я не знал о java [но вы можете его реализовать].

Изменить: ваш текущий подход O(n sqrt(n)), но с моим соглашением он может быть в одном порядке! но более высокая производительность, на самом деле порядок O(n sqrt(n) / log (n) + n log(n/log(n))) и потому, что log (n) меньше, чем n^Epsilon, лучше сказать это O(n sqrt(n)), но, как вы видите, это будет быстрее работать с журналом (n).

Также лучше сделать i-2, а не i--, а также выполнить дополнительную проверку при запуске, чтобы быстрее запустить алгоритм 2 * log (n).

Ответ 2

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

Статья в Википедии (содержит псевдокод)

Чтобы сделать это рекурсивно, возможно, Решетка Eratosthenes может быть реализована рекурсивно. Эта страница может быть полезна, поскольку она, как представляется, обсуждает рекурсивную реализацию.

Ответ 3

Вам нужно сито Forever, вот код для рекурсивного простого тестера, я думаю, что он достаточно эффективен, потому что ему нужно только проверить основные факторы, дайте мне знать, что вы думаете;)

Кстати, я бы не пробовал его с чем-нибудь выше байта, кажется, что у него есть что-то более 100.

public boolean isPrime(byte testNum)
{
    if ( testNum <= 1 )
        return false;
    for ( byte primeFactor = 2; primeFactor < testNum; primeFactor++ )
        if ( isPrime(primeFactor) )
            if ( testNum % primeFactor == 0 )
                return false;
    return true;
}

Ответ 4

Во-первых, если вы хотите сгенерировать большие простые числа (в отличие от тестовых целых чисел для примитивности), тогда Теорема Поклингтона пригодится. Эта теорема допускает быстрый тест прочности для кандидата p, если вы знаете достаточно простых коэффициентов p-1. Следовательно, возможен следующий метод: Генерируйте несколько простых чисел, вычислите подходящий кратный их продукт и проверите с помощью теоремы Поклингтона. Если вы хотите найти большие простые числа (например, для криптосистемы RSA), вам придется применить этот метод рекурсивно для генерации коэффициентов p-1.

В приведенном выше описании отсутствует немало деталей. Но метод был проанализирован в глубину. Я думаю, что этот документ был самым быстрым методом, если он был опубликован, хотя с тех пор прошло некоторое время, и кто-то мог его улучшить.

P.Mihailescu. "Быстрое генерирование пропущенных простых чисел с использованием поиска в арифметических прогрессиях", Материалы CRYPTO 94, Примечания к лекциям в области компьютерных наук vol 939, Springer 1994, pp. 282-293.

Ответ 5

Почему рекурсивно?

Используйте лучший алгоритм генерации числа чисел, такой как Sieve of Eratoshenes или даже лучшее сито Аткина.