Algorithms
Comments 29
+4
>Заранее ведь неизвестно, сколько надо просеять чисел, чтобы найти 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.
0
На практике удобно использовать неравенство (не асимптотику, верную лишь в пределе!)
Pn < n (ln n + ln ln n − ½) при n > 20, где Pnn-е простое число.
UFO landed and left these words here
+6
Для этого надо все-таки учить алгебру в объеме, превышающем школьную программу.
+1
Что? Пусть x = p*q — проверяемое число, где p — простое, а q — возможно составное. Хотя бы одно из этих чисел меньше либо равно \sqrt{x}. Это число мы и найдём в качестве делителя.
-2
Мне кажется тут:
Хотя бы одно из этих чисел меньше либо равно \sqrt{x}.
-1
Я вот уже получаю второе высшее, но до сих пор ни один преподаватель по математике об этом не говорил.
0
Вы абсолютно правы. В окончательном варианте, который я не стал здесь приводить, я сделал именно так. И все же конечный результат по времени — неудовлетворительный.
0
Также обычно рассматривают числа виде 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% от всех)
0
Результаты изменятся.

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

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

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

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

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

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

«Программа хорошо документирована на языке C» — это для башорга, а не статей от которых ожидается хоть слегка научная правильность.
-1
Поясните, пожалуйста, в чем разница записи алгоритма на языке C++ и на любом другом формальном языке (допустим математическом).
0
Математический язык имеет строго определённую и простую семантику. Язык C++ имеет очень сложную и местами неопределённую (undefined behavior) семантику.
+1
Описание алгоритмов будет неполным без указанием размера требуемой памяти. Ведь компромисс быстродействие/используемая память встречается практически в каждой задаче.
0
Решето Сундарама реализовывать нет смысла — оно медленнее Эратосфена.
0
Листинги смотрятся коряво, пришлось вручную перенести в html-файл.
Станно, что мой haswell 4590 просчитал 100тыс за 9.7сек, а 1млн за 123.5 сек, что примерно в 400 раз хуже, чем у автора. Что у него за компьютер?
Only those users with full accounts are able to leave comments., please.