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

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

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 .

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

Самый быстрый алгоритм для общего тестирования простых чисел - 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))), Я предварительно вычисляю ложные срабатывания (см. Числа Кармайкл ) и выполняю двоичный поиск. Это, безусловно, самый быстрый тест, который я когда-либо проводил, единственный недостаток - ограниченный диапазон.

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

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

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