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

Адаптация и следование GateKiller, вот окончательная версия, которую я использовал.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

Это - в основном то же, но я добавил "повреждение на Sqrt" предложение и менял некоторые переменные, чтобы заставить его соответствовать лучше для меня. (Я работал над Euler и нуждался в 10001-м начале)

Решето Эратосфена является способом пойти, из-за он - простота и скорость. Моя реализация в процессорное время C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    unsigned int lim, i, j;

    printf("Find primes upto: ");
    scanf("%d", &lim);
    lim += 1;
    bool *primes = calloc(lim, sizeof(bool));

    unsigned int sqrtlim = sqrt(lim);
    for (i = 2; i <= sqrtlim; i++)
        if (!primes[i])
            for (j = i * i; j < lim; j += i)
                primes[j] = true;

    printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
    for (i = 2; i < lim; i++)
        if (!primes[i])
            printf("%d\n", i);

    return 0;
}

для нахождения начал (на Pentium Двухъядерные 1,6 ГГц E2140, с помощью одноядерного)

~ 4 с для lim = 100,000,000

Я адаптировал код, найденный на 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 взяло rountine приблизительно 1 минута для выполнения.

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

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

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

Используя 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.

@Matt: журнал (журнал (10000)) ~2

От статьи Википедии (который Вы процитировали) Решето Atkin:

Это решето вычисляет начала до N использование O(N/log log N) операции с только N <глоток> 1/2+o (1) биты памяти. Это немного лучше, чем решето Эратосфена, которое использует O(N) операции, и O (N <глоток> 1/2 (журнал регистрируются, N) / регистрируют N) биты памяти (A.O.L. Atkin, D.J. Bernstein, 2004) . Эти асимптотические вычислительные сложности включают простую оптимизацию, такую как факторизация колеса и разделение вычисления к меньшим блокам.

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

Ахим Flammenkamp записал в Решето Эратосфена :

процитированный:

@num1

Для интервалов, больше о 10^9, конечно, для тех> 10^10, Решето Эратосфена, превзойден по характеристикам Решетом Atkins и Bernstein, который использует неприводимые бинарные квадратичные формы. Посмотрите их статью для получения информации о фоне, а также абзац 5 W. Кандидатская диссертация Голуэя.

Поэтому для 10_000 Решето Эратосфена может быть быстрее тогда Решето Atkin.

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

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 + " ");
    }
}

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

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

Я рекомендую решето, или Решето Эратосфена или Решето Atkin.

решето или Eratosthenes являются, вероятно, самым интуитивным методом нахождения списка начал. В основном Вы:

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

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

решето Atkin использует аналогичный подход, но к сожалению я не знаю достаточно об этом, чтобы объяснить его Вам. Но я действительно знаю, что алгоритм, который я связал, занимает 8 секунд для выяснения всех начал до 1 000 000 000 на древнем Pentium II 350

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

Решето Исходного кода Atkin: http://cr.yp.to/primegen.html

Это - старый вопрос, но существует что-то здесь общие пропавшие без вести...

Для начал это небольшое, испытательное подразделение не что медленно... существует только 25 начал под 100. Со столь немногими началами для тестирования, и такие маленькие начала мы можем вытащить аккуратный прием!

, Если взаимно-простого к b, то GCD b = 1. Взаимно-простой. Забавное слово. Средства это не совместно использует никакие простые множители . Мы можем таким образом протестировать на делимость несколькими началами с одним вызовом GCD. Сколько? Ну, продуктом первых 15 начал являются меньше, чем 2^64. И продуктом следующих 10 являются также меньше, чем 2^64. Это - все 25, что нам нужно. Но действительно ли это стоит того?

Позволяют нам видеть:

check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes

a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes

Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)

А 6 улучшений сгиба там.

(length должен вынудить список быть вычисленным. Значением по умолчанию Haskell печатает вещи 1 символ Unicode за один раз и поэтому на самом деле печать , список будет или доминировать над временем или доминировать над объемом фактического используемого кода.)

, Конечно, это работает в GHCi - repl выполнение интерпретируемого кода - на старом ноутбуке, и это не интерпретирует ни одного из этих чисел как int64 с или даже BigInt с, ни будет это, даже если Вы спросите это к (хорошо, Вы можете сила это, но это ужасно и действительно не помогает). Это интерпретирует каждое число там, как обобщено подобный Целому числу вещи, которые могут быть специализированы к некоторому конкретному типу через поиск по словарю, и это пересекает связанный список (который не сплавлен далеко здесь, поскольку это не компилируется), 3 раза. Интересно, рука, плавящая два фильтра на самом деле, замедляет его в REPL.

Позволяют нам скомпилировать его:

...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total   time    0.000s  (  0.004s elapsed)

Используя отчет РТС, потому что Windows. Некоторые строки обрезали, потому что они не релевантны - они были другими данными GC или измерениями только части выполнения, и вместе составляют в целом 0,004 с (или меньше). Это - также не сворачивание констант, потому что Haskell на самом деле не делает большой части этого. Если мы постоянный сгиб сами (main = print 10000), мы получаем существенно более низкое выделение:

...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total   time    0.000s  (  0.001s elapsed)

Буквально как раз для загрузки времени выполнения затем узнайте, там не имеет отношения, но распечатайте число и выход. Давайте добавим факторизацию колеса:

wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel

Total   time    0.000s  (  0.003s elapsed)

Сокращенный приблизительно 1/3-й относительно нашей ссылки main = print 10000, но существует определенно комната для большего количества оптимизации. Это на самом деле остановилось для выполнения GC там, например, в то время как с тонкой настройкой не должно быть никакого использования "кучи". По некоторым причинам компиляция для профилирования здесь на самом деле сокращает время выполнения к 2 миллисекундам:

Tue Nov 12 21:13 2019 Time and Allocation Profiling Report  (Final)

   Primes.exe +RTS -p -RTS

total time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)
total alloc =     967,120 bytes  (excludes profiling overheads)

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

Сито кажется неправильный ответ. Сито дает вам простые числа от до числа N , а не первых N простых чисел. Запустите @Imran или @Andrew Szeto, и вы получите простые числа до N.

Сито все еще можно будет использовать, если вы продолжите пытаться использовать сита для все больших чисел, пока не достигнете определенного размера вашего набора результатов, и использовать некоторое кеширование чисел уже получены, но я считаю, что это все равно будет не быстрее, чем решение, подобное @ Pat's.

Вот Сито Эратосфена, которое я написал в 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
}

В Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p