Алгоритм нахождения N первых простых чисел — Решето Аткина

[olegi]

А где бывает прикладное применении этой задачи?

[Noobster]

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

[olegi]

ясно, спасибо.

[Invizory]

Ну это все понятно, куда интересней другой вопрос — а лично вы в каких целях использовали этот алгоритм?

[Noobster]

Лично я — в учебных, если быть честным.

[Zlobober]

В целях попадания на хабр, ясно же :-)

[mihaild]

На GCJ один раз решето Аткина меня спасло.

[Zlobober]

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

Какого года и какая именно задачка, если не секрет?

[mihaild]

Использовать этот архив неспортивно:)
Не помню, хоть убейте. Помню, что написал его в template, где-то использовал, после контеста проверил — с решетом Эратосфена мог бы не успеть.

[olegi]

*применение

[Colwin]

Реализация есть — описания алгоритма нету.
Минус Вам, уважаемый. :-)

[Noobster]

Спасибо, учту на будущее.

Описание алгоритма можно найти на английской Википедии.

[bya]

На вики алгоритм изложен короче и яснее, а приведенный там код на C дал для значения 8 000 000 с выводом всех чисел файл время 0m0.280s. Дальше правда не считает, наверно связано с тем, что использует тип int. Время расчета без вывода в файл 0m0.190s.

Машина
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
CPU(s): 2
Vendor ID: GenuineIntel
CPU family: 6
CPU MHz: 2500.000
L1d cache: 32K
L1i cache: 32K
L2 cache: 2048K