Нахождение всех простых чисел от 1 до n, алгоритм

[Spook]

Начальная задача такова: найти простые числа до $n$ за наименьшее время.

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

[ИСН]

Алгоритм называется "решето Эратосфена", и я не представляю, что может быть быстрее, если речь идёт об интервале (1,n).
Если не с единицы, то могут быть нюансы.

[Руст]

Когда ищется в полном интервале от 1 до n, не существует лучшего алгоритма чем Решето.
Запишем первое простое $p_0=2$ и запишем все нечётные (присваиваем бинарной - битовой переменной на этих числах f(k)=1).
Берём первое ещё не проверенное число, если f(p)=1 число простое, иначе пока не нашли проверяем дальше. Если $p^2<n$, то числам начиная от $k=p^2$ присваем $while(k<=n), \ f(k)=0,k+=2p$. Если $p^2>n$ то дальше не требуется вычеркивать и все числа $k,f(k)=1$ простые.

[juna]

Есть и альтернативные экзотические способы. Рассмотрим таблицу:

4  7   10  13  16  19...
7  12  17  22  27  32...
10 17  24  31  38  45...
13 22  31  40  49  58...
16 27  38  49  60  71...
19 32  45  58  71  84...

Если число $n$ встречается в этой таблице, то число $2n+1$ - составное, в противном случае число $2n+1$ - простое.
Причем в этой таблице из простых не встречаются только простые числа Софи Жермен.

[e7e5]

Руст писал(а):

Когда ищется в полном интервале от 1 до n, не существует лучшего алгоритма чем Решето.

Как доказать это утверждение?

[maxal]

juna писал(а):

Есть и альтернативные экзотические способы. Рассмотрим таблицу:

4  7   10  13  16  19...
7  12  17  22  27  32...
10 17  24  31  38  45...
13 22  31  40  49  58...
16 27  38  49  60  71...
19 32  45  58  71  84...

Если число $n$ встречается в этой таблице, то число $2n+1$ - составное, в противном случае число $2n+1$ - простое.

Это т.н. решето Сундарама.

Добавлено спустя 25 минут 2 секунды:

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

V. Ramaswami Aiyar (1934). "Sundaram's Sieve for Prime Numbers". The Mathematics Student 2: 73.



Из малоизвестного индийского журнала The Mathematics Student, информация об этом решете была перепечатана в 1941 году в более известном научно-популярном журнале Scripta Mathematica, откуда она потом в 1950-х годах попала в книжку Кордемского Математическая смекалка. Именно эта книга способствовала дальнейшей популяризации этого решета в СССР и за его пределами (книга переводилась как минимум на немецкий язык).

[Батороев]

Еще одно решето до кучи... (с)

Имеется линейка с нанесенными делениями натуральных чисел.
Параллельно первой линейке обратным концом дискретно по делениям выдвигаем линейку с нанесенными на ней делениями квадратов натуральных чисел $ k_i^2 $.
Нечетные деления первой линейки, совпадающие с делениями второй, отмечаем меткой.
Деления (натуральные числа) первой линейки, меньшие $ 2k_i - 1 $, имеющие одну метку, "отсеиваем" в список простых чисел.
В окончательном списке единичку поменяем на двойку.

[Spook]

Спасибо, буду знать. Возник вот еще вопрос: известны ли кому-нибудь алгоритм для проверки числа на простоту, а также алгоритм разложения на простые множители? (первый, конечно, следует из второго, но вдруг как-то можно ускорить).

Руст, интересно, какая сложность у этого алгоритма (решето Эратосфена)? Линейная?

[Brukvalub]

Кстати, есть еще алгоритм решета Аткина : http://ru.wikipedia.org/wiki/%D0%A0%D0% ... 0%BD%D0%B0

Spook в сообщении #136356 писал(а):

Возник вот еще вопрос: известны ли кому-нибудь алгоритм для проверки числа на простоту, а также алгоритм разложения на простые множители? (первый, конечно, следует из второго, но вдруг как-то можно ускорить).

Они описаны, например, вот здесь: Василенко О.Н. — Теоретико-числовые алгоритмы в криптографии

[Руст]

Spook писал(а):

Спасибо, буду знать. Возник вот еще вопрос: известны ли кому-нибудь алгоритм для проверки числа на простоту, а также алгоритм разложения на простые множители? (первый, конечно, следует из второго, но вдруг как-то можно ускорить).

Руст, интересно, какая сложность у этого алгоритма (решето Эратосфена)? Линейная?

Сложность алгоритма $O(nlnln(n))$.
Первый гораздо проще имеются доказанные полиномиальные (относительно ln(n)) алгоритмы. Однако второй вряд ли имеет полиномиальную сложность для общего числа.

[Spook]

Brukvalub,Руст, спасибо.

Кто-нибудь может посоветовать литературу по таким алгоритмам (да и вообще, по алгоритмам: что лучше почитать), особенно интересно оценивание сложности.

[Бодигрим]

Цитата:

(да и вообще, по алгоритмам: что лучше почитать)

По анализу алгоритмов, наверное, можно читать "Искусство программирования" Кнута. Там есть и глава про проверку на простоту.

[Someone]

Spook в сообщении #136356 писал(а):

Возник вот еще вопрос: известны ли кому-нибудь алгоритм для проверки числа на простоту

http://primes.utm.edu/

[maxal]

Тест Миллера-Рабина и далее по ссылкам...

[Руст]

Устаревшиеся сведения. При выполнении обобщённой гипотезы Римана достаточно перебирать простые а от 2 до $2(\ln m)^2$. Имеются ещё достаточные количества проверок вплоть до $m=10^{15}$, что удобно при использовании не очень больших простых.