Алгоритмы поиска простых чисел

[third112]

сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до 10^8.

Недавно показал, что на довольно скромном ПК решетом Эратосфена можно быстро просеить в 10 раз больше.

Про линейный алгоритм решета Эратосфена см.

[ky0]

Пользуясь случаем, в очередной раз приглашаю всех заинтересованных в нашу команду по поиску простых чисел Мерсенна. 52-ое уже на подходе, я чувствую это :)

P.S. — сейчас GIMPS постепенно переходит от LL-теста к PRP с коррекцией ошибок, ввиду значительно большей толерантности последнего к аппаратным ошибкам.

[IgnisDeus]

Простите, но где 2¹¹-1

[ky0]

А зачем оно там?

[IgnisDeus]

А разве это не число Мерсенна?

[ky0]

Число. Но простое ли?

[IgnisDeus]

Уфф, плохо проверил

[korjavin]

Отличная статья

[red_void]

Число называется простым, если оно имеет только два различных делителя: единицу и само себя

Правильно ли я понимаю, что -1, согласно этому определению — простое число? ;)

[NeverWalkAloner]

Справедливое замечание) Исправил, спасибо!

[PavelMSTU]

Всё в одном. Хороший пост. Плюсанул.

[aafin]

В 2002 придумали ещё один.