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

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

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

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

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

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/

Сито из исходного кода Atkin: http://cr.yp.to/primegen.html

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

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

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

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

import Data.List.Ordered (minus, union)

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)). Сложность по времени значительно улучшается (примерно до логарифмического коэффициента выше оптимального) за счет сворачивания в древовидную структуру, а сложность пространства существенно улучшается при производстве многоступенчатых простых чисел , в}

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).}

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

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

Это сито вычисляет простые числа до N, используя O(N/log log N)операции только с N ^{1/2 + o (1)} битами памяти. Это немного лучше, чем сито Эратосфена, которое использует O(N) операции и O (N ^1/2 (log log N) / log N) бит памяти (AOL Atkin, DJ Bernstein, 2004) . Эти асимптотические вычислительные сложности включают в себя простые оптимизации, такие как разложение на множители, и разбиение вычислений на более мелкие блоки.

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

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

цитируется:

@ num1

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

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

Чтобы ответить на OP, код prime_sieve.c (цитируется num1)

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

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

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

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

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

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

Сито Эратосфена - это путь, благодаря своей простоте и скорости. Моя реализация в 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 Dual Core E2140 1.6 ГГц, используя одноядерный)

~ 4 секунды для лимита = 100 000 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;
    }

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

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

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

В питоне

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

Deque решета алгоритма упомянутого BenGoldberg заслуживает более подробного рассмотрения, не только потому , что это очень элегантно , но и потому , что иногда может быть полезны на практике ( в отличии от Решета Аткина, который является чисто академическим упражнением).

Основная идея алгоритма удаления сита состоит в том, чтобы использовать небольшое скользящее сито, которое является достаточно большим, чтобы содержать хотя бы одно отдельное кратное число для каждого из «активных» простых факторов в настоящее время - то есть тех простых чисел, квадрат которых не превышает наименьшее число В настоящее время представлено движущееся сито. Другое отличие от SoE состоит в том, что сито deque хранит фактические факторы в слотах композитов, а не в логических значениях.

Алгоритм расширяет размер окна сита по мере необходимости, что приводит к достаточно равномерной производительности в широком диапазоне, пока сито не начнет заметно превышать емкость кэша L1 ЦП. Последнее простое число, которое подходит полностью, составляет 25 237 523 (1579 791-е простое число), что дает приблизительную приблизительную цифру для разумного рабочего диапазона алгоритма.

Алгоритм довольно прост и надежен, и его производительность даже в гораздо более широком диапазоне, чем у несегментированного сита Эратосфена. Последнее намного быстрее, пока его сито полностью помещается в кэш, то есть до 2 ^ 16 для сита только для коэффициентов с размерами байт. Затем его производительность падает все больше и больше, хотя он всегда остается значительно быстрее, чем deque, несмотря на помехи (по крайней мере, в скомпилированных языках, таких как C / C ++, Pascal или Java / C #).

Вот рендеринг алгоритма deque sieve в C #, потому что я нахожу этот язык - несмотря на его многочисленные недостатки - гораздо более практичным для прототипирования алгоритмов и экспериментов, чем чрезвычайно громоздкий и педантичный C ++. (Sidenote: я использую бесплатный LINQPad, который позволяет погружаться прямо, без всякой путаницы с настройкой проектов, make-файлов, каталогов или еще чего-то, и это дает мне ту же степень интерактивности, что и приглашение Python).

C # не имеет явного типа deque, но обычный List<int>работает достаточно хорошо для демонстрации алгоритма.

Примечание: эта версия не использует deque для простых чисел, потому что просто не имеет смысла выталкивать sqrt (n) из n простых чисел. Что хорошего в том, чтобы удалить 100 простых чисел и оставить 9900? По крайней мере, таким образом все простые числа собраны в аккуратный вектор, готовый для дальнейшей обработки.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

Вот две вспомогательные функции:

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

Вероятно, самый простой способ понять алгоритм - это представить его как специальное сегментированное сито Эратосфена с размером сегмента 1, сопровождаемое областью переполнения, где простые числа останавливаются при прохождении через конец сегмента. За исключением того, что единственная ячейка сегмента (aka sieve[0]) уже была просеяна, когда мы до нее добрались, потому что она переехала, когда была частью области переполнения.

Число, которое представлено символом sieve[0], хранится в sieve_base, хотя sieve_frontили window_baseбудет также хорошим именем, которое позволяет проводить параллели с кодом Бена или реализациями сегментированных / оконных сит.

Если sieve[0]содержит ненулевое значение, то это значение является фактором sieve_base, который, таким образом, может быть признан составным. Поскольку ячейка 0 кратна этому коэффициенту, легко вычислить ее следующий переход, который просто равен 0 плюс этот коэффициент. Если эта ячейка уже занята другим фактором, тогда мы просто добавляем фактор снова и так далее, пока не найдем множитель фактора, где в данный момент нет другого фактора (расширяя сито при необходимости). Это также означает, что нет необходимости хранить текущие рабочие смещения различных простых чисел от одного сегмента к другому, как в обычном сегментированном сите. Всякий раз, когда мы находим фактор sieve[0], его текущее рабочее смещение равно 0.

Текущий премьер вступает в игру следующим образом. Простое может стать текущим только после своего вхождения в поток (то есть, когда оно было обнаружено как простое, потому что не помечено каким-либо фактором), и оно будет оставаться текущим до точного момента, который sieve[0]достигает его квадрата. Все нижние кратные этого простого числа должны быть удалены из-за активности меньших простых чисел, как в обычном SoE. Но ни одно из меньших простых чисел не может оторваться от квадрата, поскольку единственным фактором квадрата является само простое число, и на данный момент он еще не находится в обращении. Это объясняет действия, предпринятые алгоритмом по делу sieve_base == current_prime_squared(что sieve[0] == 0, кстати, подразумевает ).

Теперь случай sieve[0] == 0 && sieve_base < current_prime_squaredлегко объясним: это означает, что он sieve_baseне может быть кратным ни одному из простых чисел, меньших текущего простого числа, иначе он был бы помечен как составной. Я также не могу быть большим кратным текущего простого числа, поскольку его значение меньше квадрата текущего простого числа. Следовательно, это должно быть новое простое число.

Алгоритм, очевидно, основан на Сите Эратосфена, но, очевидно, он сильно отличается. Сито Эратосфена получает превосходную скорость благодаря простоте своих элементарных операций: одно добавление индекса и одно хранилище для каждого шага операции - это все, что он делает в течение длительных периодов времени.

Вот простое несегментированное сито эратосфена, которое я обычно использую для просеивания простых чисел фактора в пределах короткого диапазона, т.е. до 2 ^ 16. Для этого поста я изменил его на работу за 2 ^ 16, подставляя intдляushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

При просеивании первых 10000 простых чисел будет превышен типичный кэш L1 размером 32 КиБайта, но функция все еще очень быстра (доля миллисекунды даже в C #).

Если вы сравните этот код с ситом deque, то легко заметить, что операции сита deque намного сложнее, и он не может эффективно амортизировать свои накладные расходы, потому что он всегда делает кратчайшие возможные пересечения подряд (ровно одно вычеркивание после пропуска всех вычеркнутых кратных значений).

Примечание: код на C # используется intвместо того, uintпотому что новые компиляторы имеют привычку генерировать некачественный код uint, вероятно, для того, чтобы подтолкнуть людей к целым числам со знаком ... В версии C ++ кода выше, который я использовал unsignedповсюду, естественно; эталонный тест должен был быть в C ++, потому что я хотел, чтобы он базировался на предположительно адекватном типе deque (при использовании std::deque<unsigned>не было никакого увеличения производительности unsigned short). Вот цифры для моего ноутбука Haswell (VC ++ 2015 / x64):

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

Примечание: время C # почти в два раза больше времени C ++, что очень хорошо для C #, и это показывает, что List<int>это не дурак, даже если его используют как deque.

Простой ситовый код по-прежнему уносит деку из воды, даже если он уже работает за пределами своего нормального рабочего диапазона (размер кэш-памяти L1 превышен на 50%, при этом происходит переполнение кеша). Доминирующая часть здесь - это считывание просеянных простых чисел, и это не сильно влияет на проблему с кешем. В любом случае функция была разработана для просеивания факторов факторов, то есть уровня 0 в трехуровневой иерархии сит, и обычно она должна возвращать только несколько сотен факторов или небольшое количество тысяч. Отсюда и его простота.

Производительность может быть улучшена более чем на порядок при использовании сегментированного сита и оптимизации кода для извлечения просеянных простых чисел (пошаговый мод 3 и развернутый дважды, или мод 15 и развернутый один раз), и, тем не менее, может быть увеличена производительность из код с использованием колеса мод 16 или мод 30 со всеми обрезками (то есть полное развертывание для всех остатков). Нечто подобное объясняется в моем ответе Найти простое простое число в Code Review, где обсуждалась аналогичная проблема. Но трудно понять смысл улучшения времени за миллисекунды для одноразовой задачи ...

Для краткости рассмотрим следующие моменты времени C ++ для просеивания до 100 000 000:

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

В отличие от этого, сегментированное сито в C # с несколькими наворотами делает ту же самую работу за 95 мс (нет доступных таймингов C ++, так как в настоящее время я выполняю вызовы кода только в C #).

В интерпретируемом языке, таком как Python, все может выглядеть совершенно иначе и, возможно, даже разделение). Это неизбежно подорвет преимущество простоты Решета Эратосфена, и это может сделать решение для настила немного более привлекательным.

Кроме того, во многих случаях, сообщаемых другими респондентами в этой теме, вероятно, преобладает время выхода . Это совершенно другая война, где моим главным оружием является простой класс, подобный этому:

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

Это занимает менее 1 мс для записи 10000 (отсортированных) чисел. Это статический класс, потому что он предназначен для текстового включения в заявки на кодирование, с минимумом суеты и нулевых накладных расходов.

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

Вот мой код VB 2008, который находит все простые числа <10 000 000 за 1 минуту 27 секунд на моем рабочем ноутбуке. Он пропускает четные числа и ищет только те простые числа, которые являются <квадратом тестового числа. Он предназначен только для поиска простых чисел от 0 до значения часового.

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub

Следующий код Mathcad вычисляет первый миллион простых чисел менее чем за 3 минуты.

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

Вот решение C ++, использующее форму SoE:

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

Обратите внимание, что эта версия сита может вычислять простые числа бесконечно.

Также обратите внимание, что STL dequeзанимает O(1)время , чтобы выполнить push_back, pop_frontи произвольный доступ , хотя индексация.

resizeОперация занимает O(n)время, где nэто число элементов добавляется. Из-за того, как мы используем эту функцию, мы можем рассматривать эту небольшую константу.

Тело whileцикла in my_insertвыполняется O(log log n)раз, где nравно переменной maybe_prime. Это потому, что выражение условия whileбудет иметь значение true один раз для каждого простого множителя maybe_prime. Смотрите " Функция делителя " в Википедии.

Умножение на количество раз, которое my_insertвызывается, показывает, что O(n log log n)для составления списка nпростых чисел требуется время ... что неудивительно, что временная сложность, которую должен иметь Сито Эратосфена.

Однако, в то время как этот код является эффективным, это не самым эффективным ... Я бы настоятельно рекомендую использовать специализированную библиотеку для генерации простых чисел, таких как primesieve . Любое действительно эффективное, хорошо оптимизированное решение потребует больше кода, чем кто-либо хочет ввести в Stackoverflow.

При использовании Sieve of Eratosthenes вычисления выполняются намного быстрее по сравнению с «общеизвестным» алгоритмом простых чисел.

Используя псевдокод из его вики ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), я смогу найти решение на C #.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes (100000000) занимает 2 с и 330 мс.

ПРИМЕЧАНИЕ . Значение может отличаться в зависимости от технических характеристик оборудования.

Я трачу некоторое время на написание программы, вычисляющей много простых чисел, и этот код я использую для вычисления текстового файла, содержащего первые 1.000.000.000 простых чисел. Это на немецком языке, но интересная часть - метод calcPrimes(). Простые числа хранятся в массиве под названием Primzahlen. Я рекомендую 64-битный процессор, потому что вычисления с 64-битными целыми числами.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}

Я написал это с использованием Python, так как я только начал изучать его, и он прекрасно работает. Десятый тысячный штрих генерируется этим кодом, как указано в http://primes.utm.edu/lists/small/10000.txt . Чтобы проверить, nявляется ли простое число или нет, разделите nна числа от 2до sqrt(n). Если любой из этого диапазона чисел идеально делится, nто это не простое число.

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))

Я работал над поиском простых чисел около года. Вот что я нашел самым быстрым:

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

1902465190909 нано секунд, чтобы добраться до 2147483629, начиная с 2.

Вот мой код, который находит первые 10000 простых чисел за 0,049655 с на моем ноутбуке, первые 1 000 000 простых чисел менее чем за 6 секунд и первые 2 000 000 простых чисел за 15 секунд.
Небольшое объяснение. Этот метод использует 2 метода, чтобы найти простое число

1. во-первых, любое не простое число является составной из кратных простых чисел, поэтому этот тест кода путем деления номера теста на более простые простые числа вместо любого числа уменьшает вычисление как минимум в 10 раз для числа из 4 цифр и даже больше для большее число
2. во-вторых, помимо деления на простое число, оно делит только на простые числа, которые меньше или равны корню проверяемого числа, еще больше сокращая вычисления, это работает, потому что любое число, большее чем корень числа, будет иметь номер аналога, который должно быть меньше, чем корень числа, но так как мы уже проверили все числа, меньшие, чем корень, поэтому нам не нужно беспокоиться о числе больше, чем корень проверяемого числа.

Пример выходных данных для первого простого числа в 10000
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Вот код на языке C, введите 1, а затем 10 000, чтобы распечатать первые 10000 простых чисел.
Изменить: я забыл, что это содержит библиотеку математики, если вы находитесь на Windows или Visual Studio, чем это должно быть хорошо, но в Linux вы должны скомпилировать код, используя аргумент -lm, или код может не работать
Пример: gcc -Wall -o "% e ""% f "-lm

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}

Вот код, который я сделал:

enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}

Использование метода Array.prototype.find () в Javascript. 2214,486 мс

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms

Я могу дать вам несколько советов, вы должны реализовать это.

1. За каждое число получите половину этого числа. Например, для проверки 21, только получить остаток, разделив его от диапазона 2-10.
2. Если это нечетное число, делите только на нечетное число, и наоборот. Например, для 21, разделите только на 3, 5, 7, 9.

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

Поскольку вы хотите только первые 10000 простых чисел, а не кодировать сложный алгоритм, я предложу следующее

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

теперь вызов прост, как вам нужно

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}

Это старый вопрос, но здесь есть что-то, чего всем не хватает ...

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

Если a взаимно прост с b, то gcd ab = 1. Простое. Веселое слово. Означает, что это не имеет общих факторов . Таким образом, мы можем проверить делимость на несколько простых чисел одним вызовом GCD. Как много? Что ж, произведение первых 15 простых чисел составляет менее 2 ^ 64. И произведение следующих 10 также меньше 2 ^ 64. Это все, что нам нужно. Но стоит ли это того?

Давайте посмотрим:

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, выполняющем интерпретированный код - на старом ноутбуке, и оно не интерпретирует ни одно из этих чисел как int64s или даже BigInts, и не будет, даже если вы попросите его (ну, вы можете принудительно заставить его , но это некрасиво и не очень помогает). Он интерпретирует каждое отдельное число как обобщенные целочисленные объекты, которые могут быть специализированы для определенного типа через поиск по словарю, и пересекает связанный список (который не слит здесь, поскольку он не скомпилирован) 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)

Использование отчета RTS, потому что Windows. Некоторые линии обрезаны, потому что они не релевантны - они были другими данными ГХ или измерениями только части выполнения и вместе составляют в сумме 0,004 с (или меньше). Это также не постоянное сворачивание, потому что Хаскелл фактически не делает этого. Если мы будем постоянно сворачивать себя ( 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)

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

using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}