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

Question

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

Answer 1

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

Answer 2

Решето Аткина-это, наверное, то, что вы ищете, его верхняя граница времени выполнения составляет o(Н/журнала Н). Если вы только на цифры 1 больше и на 1 меньше, чем кратное 6, это может быть даже быстрее, так как все простые числа от 3 от 1 от кратных шести. Ресурс для моего заявления

Answer 3

Я рекомендую сито либо решето Эратосфена или решета Аткина. Решето Эратосфена или, вероятно, наиболее понятный способ нахождения списка простых чисел. В основном вы: Запишите список из чисел от 2 до предела все, что вы хотите, скажем, 1000. Возьмите первый номер, который не вычеркнул (для первой итерации это 2) и вычеркнуть все числа, кратные этого числа из списка. Повторите шаг 2, пока вы не дойдете до конца списка. Все номера, которые не пересекаются, являются премьер. Очевидно, есть несколько оптимизаций, которые можно сделать, чтобы этот алгоритм работать быстрее, но это основная идея. Решето Аткина использует подобный подход, но к сожалению я не знаю достаточно об этом, чтобы объяснить его вам. Но я знаю, что алгоритм я связал занимает 8 секунд, чтобы разобраться во всех простых чисел до 1000000000 на древний Пентиум второй-350 Решето Эратосфена исходный код: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/ Решето Аткина исходный код: http://cr.yp.to/primegen.html

Answer 4

Это не строго против ограничения хардкодом, но очень близко. Почему не программное скачать этот список и распечатать его, а? http://primes.utm.edu/lists/small/10000.txt

Answer 5

GateKiller, как о добавлении

break

к

if

в курсе

foreach

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

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count

Answer 6

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

primes = 2 : minus [3..] (foldr (\p r 

primes !! 10000

почти мгновенно. Ссылки: Решето Эратосфена Ричард Берд решето (см. стр. 10, 11) минус, Союз Код выше-это легко переделаны в работе на шансы только,

primes = 2 : 3 : minus [5,7..] (foldr (\p r . Сложность время значительно улучшилось (только про коэффициент выше оптимального журнала) путем складывания в древовидную структуру, и сложность пространства значительно улучшилось по производству многоступенчатых простых, в

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p 

(В Haskell скобки используются для группировки, функция вызов означал только противопоставление, (:)

является зэками для списков, и

(.)

является функциональным оператором состав:

(f . g) x = (\y ).

Answer 7

@Мэтт: журналу(log(10000)) - это ~2 Из статьи в Википедии (которую вы цитировали) решето Аткина: Это сито вычисляет простые числа до n используя операции

O(N/log log N)

с только Н1/2 О(1) бит памяти. Это немного лучше, чем решето Эратосфен, который использует

O(N)

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

O(N)

(по Эратосфену) и

O(N/log(log(N)))

(для Эткина) мы не можем сказать (для малых

N=10_000

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

10_000

решето Эратосфена может быть тогда быстрее решета Аткина. Чтобы ответить на ОП код prime_sieve.с (цитируется по

num1

)

Answer 8

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

#include

Answer 9

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

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

Это тесты, Если, на строку, состоящую из K “

1

”с, к простым не (например, является ли строка состоит из одного “

1

” или “

1

”, которое может быть выражено как N-арные продукт).

Answer 10

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

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count