Самый эффективный код для первых 10000 простых чисел?

Question

Я хочу напечатать первые 10000 простых чисел. Кто-нибудь может дать мне самый эффективный код для этого? Разъяснения:

1. Неважно, если ваш код неэффективен для n> 10000.
2. Размер кода не имеет значения.
3. Вы не можете просто жестко закодировать значения любым способом.

Answer 1

Сито Аткина - это, вероятно, то, что вы ищете, его верхняя граница времени работы O (N / log log N).

Если вы используете только числа на 1 больше и на 1 меньше, чем числа, кратные 6, это может быть даже быстрее, поскольку все простые числа выше 3 находятся на расстоянии 1 от кратного шести. Ресурс для моего заявления

Answer 2

Я рекомендую сито: Сито Эратосфена или Сито Аткина.

Сито или Эратосфен, возможно, является наиболее интуитивным методом поиска списка простых чисел. В основном вы:

1. Запишите список чисел от 2 до любого предела, скажем 1000.
2. Возьмите первое число, которое не вычеркнуто (для первой итерации это 2) и вычеркните все кратные этого числа из списка.
3. Повторяйте шаг 2, пока не дойдете до конца списка. Все числа, которые не вычеркнуты, просты.

Очевидно, что можно сделать довольно много оптимизаций, чтобы этот алгоритм работал быстрее, но это основная идея.

Сито Аткина использует аналогичный подход, но, к сожалению, я недостаточно знаю об этом, чтобы объяснить это вам. Но я знаю, что алгоритм, который я связал, занимает 8 секунд, чтобы вычислить все простые числа до 1000000000 на древнем Pentium II-350

Сито Эратосфена Исходный код: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Сито Аткина Исходный код: http://cr.yp.to/primegen.html

Answer 3

Это не строго против ограничения жесткого кода, но очень близко. Почему бы не загрузить этот список программным способом и не распечатать его?

http://primes.utm.edu/lists/small/10000.txt

Answer 4

GateKiller , как насчет добавления break к этому if в цикле foreach? Это ускорит вещи много , потому что если 6 делится на 2, вам не нужно проверять 3 и 5. (Я бы все равно проголосовал за ваше решение, если бы у меня была достаточно репутация :-) ...)

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

Answer 5

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

primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                [] primes)

primes !! 10000 почти мгновенно.

Ссылки:

• Сито Эратосфена
• Сито Ричарда Берда (см. С. 10,11)
• минус, объединение

---

_{Приведенный выше код легко настраивается на работу только по коэффициентам, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Сложность по времени значительно улучшается (примерно до коэффициента log выше оптимального) за счет сворачивания в древовидную структуру, а сложность пространства радикально улучшается путем многоступенчатого простого производства , в}

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

_{(В Haskell круглые скобки используются для группировки, вызов функции обозначается просто сопоставлением, (:) - это оператор cons для списков и (.) - оператор функциональной композиции: (f . g) x = (\y -> f (g y)) x = f (g x)).}

Answer 6

@ Matt: log (log (10000)) составляет ~ 2

Из статьи Википедии (которую вы цитировали) Сито Аткина :

Это сито вычисляет простые числа до N используя O(N/log log N) операции с только N ^{1/2 + o (1)} бит памяти. То есть немного лучше, чем сито Эратосфен, который использует O(N) операции и O (N ^1/2 (журнал журнала N) / журнал N) биты памяти (А.О.Л. Аткин, Д.Я. Бернштейн, 2004) . Эти асимптотики вычислительные сложности включают в себя простые оптимизации, такие как колесо факторизация и расщепление вычисление в меньшие блоки.

Учитывая асимптотические вычислительные сложности вдоль O(N) (для Эратосфена) и O(N/log(log(N))) (для Аткина), мы не можем сказать (для малых N=10_000), какой алгоритм, если он будет реализован, будет быстрее.

Ахим Фламменкамп написал в Сито Эратосфена :

цитируется:

@ num1

Для интервалов больше 10 ^ 9, наверняка для тех> 10 ^ 10, Сито Эратосфен превосходит Сито Аткинса и Бернштейна, которое использует неприводимый двоичный квадратичный формы. Смотрите их бумаги для фона информация, а также пункт 5 Доктор философии В. Голуэя Тезис.

Поэтому для 10_000 Сито Эратосфена может быть быстрее, чем Сито Аткина.

Для ответа на OP код: prime_sieve.c (цитируется num1)

Answer 7

Используя GMP, можно написать следующее:

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

На моем MacBook Pro с тактовой частотой 2,33 ГГц он работает следующим образом:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Расчет 1 000 000 простых чисел на одном ноутбуке:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP высоко оптимизирован для такого рода вещей. Если вы действительно не хотите понимать алгоритмы, написав свои собственные, вам будет рекомендовано использовать libGMP под C.

Answer 8

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

/^1?$|^(11+?)\1+$/

Это проверяет, если для строки, состоящей из k «1» s, k равно не простое (то есть состоит ли строка из одного «1» или любое число «1», которое может быть выражено как n -ный продукт).

Answer 9

Я адаптировал код, найденный в CodeProject , чтобы создать следующее:

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

Для проверки этого на моем сервере ASP.NET потребовалось около 1 минуты для запуска.

Answer 10

Вот Сито Эратосфена, которое я написал в PowerShell несколько дней назад. У него есть параметр для определения количества простых чисел, которые должны быть возвращены.

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}