Noobster 4 авг 2011 в 08:22

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

6 мин

19K

Алгоритмы *

Из песочницы

Комментарии 13

olegi 4 авг 2011 в 08:31

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

Noobster 4 авг 2011 в 08:32

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

olegi 4 авг 2011 в 08:36

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

Invizory 4 авг 2011 в 08:36

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

Noobster 4 авг 2011 в 08:37

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

Zlobober 4 авг 2011 в 08:46

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

mihaild 4 авг 2011 в 08:50

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

Zlobober 4 авг 2011 в 13:21

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

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

mihaild 4 авг 2011 в 20:35

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

olegi 4 авг 2011 в 08:36

*применение

Colwin 4 авг 2011 в 08:52

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

Noobster 4 авг 2011 в 08:56

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

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

bya 4 авг 2011 в 09:14

На вики алгоритм изложен короче и яснее, а приведенный там код на 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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий