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

[@halyavin]

>Заранее ведь неизвестно, сколько надо просеять чисел, чтобы найти N простых.

Довольно хорошо известно. Можно воспользоваться оценкой в ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0_%D0%A0%D0%B8%D0%BC%D0%B0%D0%BD%D0%B0, если вы верите в гипотезу Римана. Если не верите, то есть худшие оценки — mathworld.wolfram.com/PrimeNumberTheorem.html.

[@bluebyte]

Спасибо за ссылки, буду изучать.

[@halyavin]

Вот еще одна — primes.utm.edu/howmany.shtml#better. Там есть недавние результаты с конкретными оценками на n-тое простое число.

[@Bodigrim]

На практике удобно использовать неравенство (не асимптотику, верную лишь в пределе!)
P_n < n (ln n + ln ln n − ½) при n > 20, где P_n — n-е простое число.

[@gribozavr]

Что? Пусть x = p*q — проверяемое число, где p — простое, а q — возможно составное. Хотя бы одно из этих чисел меньше либо равно \sqrt{x}. Это число мы и найдём в качестве делителя.

[@gribozavr]

Где именно нестрого?

[@gribozavr]

Если x = p*q, p > \sqrt{x}, q > \sqrt{x}, то умножив почленно получим x < x.

[@bluebyte]

Я вот уже получаю второе высшее, но до сих пор ни один преподаватель по математике об этом не говорил.

[@bluebyte]

Вы абсолютно правы. В окончательном варианте, который я не стал здесь приводить, я сделал именно так. И все же конечный результат по времени — неудовлетворительный.

[@bya]

Также обычно рассматривают числа виде 6k, 6k+1, 6k+2,6k+3,6k+4,6k+5. Здесь 6=2*3 произведению первых двух простых чисел.
Из них 6k, 6k+2,6k+3,6k+4 делятся на 2 или 3.
Поэтому надо проверять на простоту только числа вида 6k+1, 6k+5 (33.3% от всех).

Это можно обобщить например рассматривая числа вида 30k, 30k+1,…
Но это становится громоздким при программирование и дает малый выигрыш
30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19,30k+23, 30k+29 (26.6% от всех)

[@ckald]

Результаты изменятся.

Сложность простого решета Эратосфена O(N*log(log(N))).
Сложность решета Аткина уже O(N/log(log(N)))

Даже учитывая медленность роста медленнорастущей функции, на больших значениях N вы ощутите разницу.

Хотя, конечно, нужно еще оценить сложность вашей модификации.

[@int02h]

if (addition)
{
..............
}
else
     addition = true;

Мне кажется, что else не нужен

[@Karde]

Когда решил задачу нахождения простых чисел (правда до N) то решил использовать веростностный тест Ферма + алгоритм грубой силы. Вместо алгоритма грубой силы можно использовать другие, но подбор другого алгоритма был не столь важен, сколько реализация вероятстного теста Ферма.

Тесты на простоту числа.

[@Rational_Yurij]

Не вижу в вашем посте именно алгоритма. Вижу его реализацию на одном конкретном языке. А алгоритма не вижу.

«Программа хорошо документирована на языке C» — это для башорга, а не статей от которых ожидается хоть слегка научная правильность.

[@bluebyte]

Поясните, пожалуйста, в чем разница записи алгоритма на языке C++ и на любом другом формальном языке (допустим математическом).

[@gribozavr]

Математический язык имеет строго определённую и простую семантику. Язык C++ имеет очень сложную и местами неопределённую (undefined behavior) семантику.

[@bluebyte]

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

[@mgn]

Описание алгоритмов будет неполным без указанием размера требуемой памяти. Ведь компромисс быстродействие/используемая память встречается практически в каждой задаче.

[@bluebyte]

Добавил информацию

[@Bodigrim]

Решето Сундарама реализовывать нет смысла — оно медленнее Эратосфена.

[@IOException]

удалено

[@DaleMartinWatson]

Кажется листинги с кодом сломались.

[@zelserg]

Листинги смотрятся коряво, пришлось вручную перенести в html-файл.
Станно, что мой haswell 4590 просчитал 100тыс за 9.7сек, а 1млн за 123.5 сек, что примерно в 400 раз хуже, чем у автора. Что у него за компьютер?