Комментарии 29
>Заранее ведь неизвестно, сколько надо просеять чисел, чтобы найти 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.
Довольно хорошо известно. Можно воспользоваться оценкой в 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.
+4
Спасибо за ссылки, буду изучать.
0
Вот еще одна — primes.utm.edu/howmany.shtml#better. Там есть недавние результаты с конкретными оценками на n-тое простое число.
0
На практике удобно использовать неравенство (не асимптотику, верную лишь в пределе!)
Pn < n (ln n + ln ln n − ½) при n > 20, где Pn — n-е простое число.
Pn < n (ln n + ln ln n − ½) при n > 20, где Pn — n-е простое число.
0
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Что? Пусть x = p*q — проверяемое число, где p — простое, а q — возможно составное. Хотя бы одно из этих чисел меньше либо равно \sqrt{x}. Это число мы и найдём в качестве делителя.
+1
Вы абсолютно правы. В окончательном варианте, который я не стал здесь приводить, я сделал именно так. И все же конечный результат по времени — неудовлетворительный.
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% от всех)
Из них 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 вы ощутите разницу.
Хотя, конечно, нужно еще оценить сложность вашей модификации.
Сложность простого решета Эратосфена O(N*log(log(N))).
Сложность решета Аткина уже O(N/log(log(N)))
Даже учитывая медленность роста медленнорастущей функции, на больших значениях N вы ощутите разницу.
Хотя, конечно, нужно еще оценить сложность вашей модификации.
0
if (addition)
{
..............
}
else
addition = true;
Мне кажется, что else не нужен
+2
Когда решил задачу нахождения простых чисел (правда до N) то решил использовать веростностный тест Ферма + алгоритм грубой силы. Вместо алгоритма грубой силы можно использовать другие, но подбор другого алгоритма был не столь важен, сколько реализация вероятстного теста Ферма.
Тесты на простоту числа.
Тесты на простоту числа.
0
Не вижу в вашем посте именно алгоритма. Вижу его реализацию на одном конкретном языке. А алгоритма не вижу.
«Программа хорошо документирована на языке C» — это для башорга, а не статей от которых ожидается хоть слегка научная правильность.
«Программа хорошо документирована на языке C» — это для башорга, а не статей от которых ожидается хоть слегка научная правильность.
+2
Описание алгоритмов будет неполным без указанием размера требуемой памяти. Ведь компромисс быстродействие/используемая память встречается практически в каждой задаче.
+1
Решето Сундарама реализовывать нет смысла — оно медленнее Эратосфена.
0
удалено
0
Кажется листинги с кодом сломались.
0
Листинги смотрятся коряво, пришлось вручную перенести в html-файл.
Станно, что мой haswell 4590 просчитал 100тыс за 9.7сек, а 1млн за 123.5 сек, что примерно в 400 раз хуже, чем у автора. Что у него за компьютер?
Станно, что мой haswell 4590 просчитал 100тыс за 9.7сек, а 1млн за 123.5 сек, что примерно в 400 раз хуже, чем у автора. Что у него за компьютер?
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм нахождения N первых простых чисел