Как создать наиболее компактное отображение n → isprime (n) до предела N?

Естественно, для bool isprime(number) была бы структура данных, которую я мог бы запросить.
Я определяю лучший алгоритм как алгоритм, который создает структуру данных с самым низким потреблением памяти для диапазона (1, N], где N - это константа.
Просто пример что я ищу: я мог бы представить каждое нечетное число одним битом, например, для заданного диапазона чисел (1, 10], начиная с 3: 1110

Следующий словарь можно сжать больше, верно «Я мог бы устранить кратные пять с некоторой работой, но числа, которые заканчиваются на 1, 3, 7 или 9, должны быть в массиве битов.

Как мне решить проблему?

145
задан Emma 29 July 2019 в 00:30
поделиться

5 ответов

Есть много способов выполнить тест на простоту .

На самом деле нет структуры данных, которую можно было бы запросить. Если у вас есть много чисел для тестирования, вам, вероятно, следует запустить вероятностный тест , поскольку они быстрее, а затем продолжить его с помощью детерминированного теста , чтобы убедиться, что число является простым.

Вы должны знать, что математика, лежащая в основе самых быстрых алгоритмов, не для слабонервных.

77
ответ дан 23 November 2019 в 22:28
поделиться

Наименьший объем памяти? Это не самый маленький, но шаг в правильном направлении.

class PrimeDictionary {
    BitArray bits;

    public PrimeDictionary(int n) {
        bits = new BitArray(n + 1);
        for (int i = 0; 2 * i + 3 <= n; i++) {
            bits.Set(i, CheckPrimality(2 * i + 3));
        }
    }

    public PrimeDictionary(IEnumerable<int> primes) {
        bits = new BitArray(primes.Max());
        foreach(var prime in primes.Where(p => p != 2)) {
            bits.Set((prime - 3) / 2, true);
        }
    }

    public bool IsPrime(int k) {
        if (k == 2) {
            return true;
        }
        if (k % 2 == 0) {
            return false;
        }
        return bits[(k - 3) / 2];
    }
}

Конечно, вы должны указать определение CheckPrimality .

-1
ответ дан 23 November 2019 в 22:28
поделиться

Согласно википедии, Сито Эратосфена имеет сложность O (n * (log n) * ( log log n)) и требует O (n) памяти - так что это неплохое место для начала, если вы не тестируете особенно большие числа.

6
ответ дан 23 November 2019 в 22:28
поделиться

Самый быстрый алгоритм для общего тестирования простых чисел - AKS . Статья в Википедии подробно описывает это и ссылается на исходную статью.

Если вы хотите найти большие числа, изучите простые числа, которые имеют особую форму, например простые числа Мерсенна .

Алгоритм, который я обычно использую (легко понять и кодировать) выглядит следующим образом (на Python):

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

Это вариант классического алгоритма O (sqrt (N)) . Он использует тот факт, что простое число (кроме 2 и 3) имеет форму 6k - 1 или 6k + 1 , и рассматривает только делители этой формы.

Иногда, если Мне очень нужна скорость, а диапазон ограничен , я реализую тест псевдопростого числа, основанный на маленькой теореме Ферма . Если мне действительно нужна большая скорость (т.е. вообще избегать алгоритма O (sqrt (N))), Я предварительно вычисляю ложные срабатывания (см. Числа Кармайкл ) и выполняю двоичный поиск. Это, безусловно, самый быстрый тест, который я когда-либо проводил, единственный недостаток - ограниченный диапазон.

206
ответ дан 23 November 2019 в 22:28
поделиться

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

Есть списки первых N простое число в Интернете с N , простирающимся как минимум до пятидесяти миллионов . Загрузите файлы и используйте их, это, вероятно, будет намного быстрее, чем любой другой метод, который вы придумаете.

Если вам нужен реальный алгоритм для создания ваших собственных простых чисел, в Википедии есть много хороших вещей для простых чисел ] здесь , включая ссылки на различные методы для этого, и основное тестирование здесь ,

26
ответ дан 23 November 2019 в 22:28
поделиться
Другие вопросы по тегам:

Похожие вопросы: