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

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

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

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

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

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

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

  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

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

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

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

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

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

Рекомендации:

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

Вышеприведенный код легко настраивается на работу только с коэффициентами, primes = 2 : 3 : minus [5,7..] (foldr (\pr -> 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 [email protected](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 (gy)) x = f (gx) ).

@Matt: log (log (10000)) – ~ 2

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

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

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

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

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

@ num1

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

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

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

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

 #include  #include  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.

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

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

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

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

Вот сито Эратосфена, которое я написал в 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  #include  #include  #include  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 ГГц, с использованием одного ядра)

~ 4s для lim = 100 000 000

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

  public IEnumerable PrimeNumbers(long number) { List primes = new List(); 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 ,

В Python

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

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

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

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

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

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

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

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

 static List deque_sieve (int n = 10000) { Trace.Assert(n >= 3); var primes = new List() { 2, 3 }; var sieve = new List() { 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 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.

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

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

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

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

 static List small_odd_primes_up_to (int n) { var result = new List(); 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 KiByte, но функция все еще очень быстрая (доля миллисекунды даже в C #).

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

Примечание: код C # использует int вместо uint потому что у более новых компиляторов есть привычка генерировать нестандартный код для uint , возможно, чтобы подтолкнуть людей к целым знакам со знаком ... В версии C ++ вышеприведенного кода я, естественно, использовал unsigned ; Тест должен был быть на C ++, потому что я хотел, чтобы он был основан на предположительно адекватном типе deque ( std::deque ; при использовании 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 #, и «t» показывает, что List является суматохой, даже если он злоупотребляет как deque.

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

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

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

 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; } } } 

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

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

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

 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  #include  typedef std::deque 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 и произвольный доступ, хотя pop_front .

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

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

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

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

Используя сито Эратосфена, вычисление происходит довольно быстро по сравнению с алгоритмом простых чисел «общеизвестный».

Используя псевдокод из его wiki ( 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(); for(var i = 3; i < n; i++) { if (mark[i]) { primes.Add(i); } } return primes.ToArray(); } 

GetPrimes(100000000) takes 2s and 330ms.

NOTE : Value might vary depend on Hardware Specifications.

I spend some time writing a program calculating a lot of primes and this is the code I’m used to calculate a text file containing the first 1.000.000.000 primes. It’s in German, but the interesting part is the method calcPrimes() . The primes are stored in an array called Primzahlen. I recommend a 64bit CPU because the calculations are with 64bit integers.

 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 zB \"Tausend\", sondern in Ziffern zB \"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 zB \"Tausend\", sondern in Ziffern zB \"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); } } } 

I have written this using python, as I just started learning it, and it works perfectly fine. The 10,000th prime generate by this code as same as mentioned in http://primes.utm.edu/lists/small/10000.txt . To check if n is prime or not, divide n by the numbers from 2 to sqrt(n) . If any of this range of number perfectly divides n then it’s not prime.

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

I have been working on find primes for about a year. This is what I found to be the fastest:

 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;ip){ return true; }else if(x%yx ==0){ return false; } y = y.next; } return true; } } 

1902465190909 nano seconds to get to 2147483629 starting at 2.

Here is my code which finds first 10,000 primes in 0.049655 sec on my laptop, first 1,000,000 primes in under 6 seconds and first 2,000,000 in 15 seconds
A little explanation. This method uses 2 techniques to find prime number

  1. first of all any non-prime number is a composite of multiples of prime numbers so this code test by dividing the test number by smaller prime numbers instead of any number, this decreases calculation by atleast 10 times for a 4 digit number and even more for a bigger number
  2. secondly besides dividing by prime, it only divides by prime numbers that are smaller or equal to the root of the number being tested further reducing the calculations greatly, this works because any number that is greater than root of the number will have a counterpart number that has to be smaller than root of the number but since we have tested all numbers smaller than the root already, Therefore we don’t need to bother with number greater than the root of the number being tested.

Sample output for first 10,000 prime number
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Here is the code in C language, Enter 1 and then 10,000 to print out the first 10,000 primes.
Edit: I forgot this contains math library ,if you are on windows or visual studio than that should be fine but on linux you must compile the code using -lm argument or the code may not work
Example: gcc -Wall -o “%e” “%f” -lm

 #include  #include  #include  #include  /* 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 ie 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); } 

Here the code that I made :


 enter code here #include  #include  #include  #include  #include  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 

Using the Array.prototype.find() method in Javascript. 2214.486 ms

 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 

I can give you some tips, you have to implement it.

  1. For each number, get the half of that number. Eg for checking 21, only obtain the remainder by dividing it from range 2-10.
  2. If its an odd number, only divide by odd number, and vice versa. Such as for 21, divide with 3, 5, 7, 9 only.

Most efficient method I got up to so far.

 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(); } } } 
  • Является ли тернарный оператор быстрее, чем условие «если»
  • Выполнение стресс-теста в веб-приложении?
  • Эффективный способ удаления строки из текстового файла
  • Улучшить производительность SQLite в секунду в секунду?
  • Структура агрегации Mongodb: используется ли индекс использования группы?
  • Самый быстрый способ удалить все непечатаемые символы из строки Java
  • Как профилировать использование памяти и производительность с помощью инструментов?
  • Как выбрать размер сетки и блока для ядер CUDA?
  • Каковы реальные накладные расходы на try / catch в C #?
  • Насколько медленны исключения .NET?
  • Неизвестные события в nodejs / v8 flashgraph с использованием perf_events
  • Interesting Posts

    Что означает один амперсанд после списка параметров объявления функции-члена?

    Соглашения ReSharper для имен обработчиков событий

    Отображение негативных меток времени в Excel 2007chart

    Кросс-браузерный способ повернуть изображение с помощью CSS?

    Как использовать источник данных JNDI, предоставленный Tomcat весной?

    Проверка подлинности электронной почты с помощью jQuery

    Что происходит с самим указателем после удаления?

    Как открыть программу с помощью командной строки в Windows 8?

    Как я могу создать резервную копию всей установки программы, а не просто вручную создавать резервные копии отдельных файлов?

    Как установить заставку для экрана блокировки Windows 8?

    Получить имя файла из URL-адреса

    org.glassfish.jersey.servlet.ServletContainer КлассNotFoundException

    POSTing ассоциация суб-ресурсов @OneToMany в Spring Data REST

    Как добавить нижний колонтитул в NavigationView – библиотеку дизайна поддержки Android?

    Есть ли у R такие операторские операции, как Perl qw ()?

    Давайте будем гением компьютера.