bluebyte Jul 21 2011 at 14:23

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

9 min

30K

Algorithms*

From sandbox

Comments 29

halyavin Jul 21 2011 at 14:46

>Заранее ведь неизвестно, сколько надо просеять чисел, чтобы найти 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 Jul 21 2011 at 14:56

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

halyavin Jul 21 2011 at 15:00

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

Bodigrim Jul 22 2011 at 03:25

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

UFO just landed and posted this here

gribozavr Jul 21 2011 at 18:24

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

UFO just landed and posted this here

gribozavr Jul 21 2011 at 18:32

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

UFO just landed and posted this here

gribozavr Jul 21 2011 at 18:38

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

UFO just landed and posted this here

bluebyte Jul 21 2011 at 19:32

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

-1

bluebyte Jul 21 2011 at 19:17

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

bya Jul 29 2011 at 09:43

Также обычно рассматривают числа виде 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 Jul 21 2011 at 15:28

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

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

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

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

int02h Jul 21 2011 at 16:06


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

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

Karde Jul 21 2011 at 18:12

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

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

Rational_Yurij Jul 21 2011 at 18:20

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

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

bluebyte Jul 21 2011 at 19:37

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

-1

gribozavr Jul 21 2011 at 22:27

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

bluebyte Jul 21 2011 at 23:01

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

mgn Jul 21 2011 at 21:56

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

bluebyte Jul 21 2011 at 23:53

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

Bodigrim Jul 22 2011 at 03:22

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

IOException Mar 13 2013 at 18:55

удалено

DaleMartinWatson Mar 5 2015 at 02:53

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

zelserg Oct 29 2015 at 20:19

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

Show the best of all time