Как найти количество простых чисел от 1 до n
Перейти к содержимому

Как найти количество простых чисел от 1 до n

  • автор:

Си: вывод простых чисел от 1 до N

В первой строке содержится целое число ��. Нужно вывести все простые числа в диапазоне от 1 до �� включительно, по одному числу в строке. Вот мой код, прога ничего не выводит и зависла по времени.
Посоветуйте, что сделать/исправить, пожалуйста.
P.S. Только начинаю изучать Си, поэтому простите мою тупость 🙂

#include int main() < int i, N, t, k; t=0; i=2; scanf("%d", &N); for (k=2; kif(t==0) < printf("%d", k); >> > > 

Отслеживать
12.6k 2 2 золотых знака 19 19 серебряных знаков 46 46 бронзовых знаков
задан 29 сен 2020 в 13:52
177 2 2 серебряных знака 16 16 бронзовых знаков

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Просто не вынесла душа такой неэффективности, как у Danis.

int main(int argc, const char * argv[]) < int N; scanf("%d",&N); if (N >= 2) puts("2"); for(int n = 3; n if (prime) printf("%d\n",n); > > 

А вообще этот вопрос уже столько раз обсасывался на RuSO, что не найти ответ — просто стыдно.

Просто ради интереса — для N = 100000 мой код работал на моей машине порядка 33 мс, код Danis для того же N — 17 секунд.

Отслеживать
27.2k 2 2 золотых знака 46 46 серебряных знаков 76 76 бронзовых знаков
ответ дан 29 сен 2020 в 14:07
222k 15 15 золотых знаков 120 120 серебряных знаков 234 234 бронзовых знака

Ну, если вы за эффективность, то: а) числа из первой сотни-двух — в таблицу, б) числа больше разрядности процессора — качаем с сайта. Ни того, ни другого я в вашем решении не вижу — что ж так неэффективно-то?!

29 сен 2020 в 14:18

Очень интеллигентно, ага! Вот всё же закон больших чисел на ruSO работает отменно — чем больше рейтинг, тем агрессивнее проталкивается свой ответ в независимости ни от чего. Печалька.

29 сен 2020 в 14:29

@0andriy Пока вижу другой закон — вахтера 🙂 — чем меньше кто-то делает для других (типа 14 ответов за 4 года), тем больше он занимается критикой тех, кто что-то делает 🙂 Переходите к следующему этапу — активному минусованию. На этом все, простите, но больше вы для меня здесь не существуете.

29 сен 2020 в 14:36

Ха-ха-ха, спасибо за подтверждение моей теории. Вы бы сначала почитали мои комментарии и ответы на смежных сайтах, впрочем. не стоит. Будьте счастливы!

29 сен 2020 в 14:37

@vp_arth Отнюдь. Не просто +6, тогда надо еще единицу туда-сюда. Да что, все совсем ох. ослепли? Там же перебор от 1 до N, не до корня даже! Не понимаю, что с вами со всеми сделалось. Просто очень хочется в кого-то плюнуть?

Как найти количество простых чисел от 1 до n

Post by Ivan Boldyrev
Поэтому никакой как таковой формулы нет. Можно, конечно, записать
алгоритм как функцию (подход Клини), но вычисление это не облегчит.

Есть весьма занимательная книжечка (перевод с немецкого):

В.Боро, Д.Цагир, Ю.Рольфс, Х.Крафт, Е.Янцен. Живые числа. Пять
экскурсий. Москва, «Мир», 1985.

Здесь в статье «Первые 50 миллионов простых чисел» Дона Цагира со
ссылкой на результаты Римана приводится формула для вычисления количества
простых чисел, не превосходящих заданного числа. Формула представляет собой
ряд по нулям дзета-функции, лежащим между 0 и 1, члены которого выражаются
через некую функцию R(x), для которой, в свою очередь, приведены два ряда:
степенной и через интегральный логарифм.
Кроме того, мне смутно помнится, что когда то я видел в «Кванте» формулу
для вычисления n-ого простого числа (не уверен, что она эффективна, тем
более, что никаких других воспоминаний об этой формуле у меня не осталось).


Всего наилучшего. В.М.Ульянов AKA Someone.
mailto:***@newmsk.tula.net
http://www.someoneltd.boom.ru/ http://home.tula.net/frazez/

P.S. Между прочим, программа Mathematica каким-то образом вычисляет и
количество простых чисел, не превосходящих заданного (функция PrimePi:
PrimePi[1000000000000]=37607912018), и n-ое простое число (функция Prime:
Prime[37607912018]=999999999989). Время вычисления на моём компьютере
(Athlon 800) — несколько секунд.

Ivan Boldyrev
2003-07-23 17:17:08 UTC
«MU» == Micron Umbarov writes:
MU> Привет всем!

Post by Ivan Boldyrev
Поэтому никакой как таковой формулы нет. Можно, конечно, записать
алгоритм как функцию (подход Клини), но вычисление это не облегчит.

MU> Кроме того, мне смутно помнится, что когда то я видел в
MU> «Кванте» формулу для вычисления n-ого простого числа (не уверен,
MU> что она эффективна, тем более, что никаких других воспоминаний об
MU> этой формуле у меня не осталось).

Да, был не прав. Купил позавчера книжку Генри Уоррен, мл.
«Алгоритмические трюки для программистов», ISBN 5-8459-0471-4.
Последняя глава посвящена как раз простым числам. Что касается сабжа,
то там приведена формула Вормелла, где используются только
арифметические операции и возведение в степень. Для p_n — n-го
простого числа — есть формулы Вилланса (их аж четыре штуки, все они
используют тригонометрию). Из формулы Вормелла можно вывести формулу
для p_n, которая тригонометрию не использует.

Если кому очень-очень нужно, пишите, вышлю формулы, набранные в
TeXовой записи.

. Работаю в сфере высоких технологий (монтажник-высотник).

Как найти количество простых чисел от 1 до n

Наиболее наивный подход к поиску простых чисел заключается в следующем. Будем брать по очереди натуральные числа n , начиная с двойки, и проверять их на простоту. Проверка на простоту заключается в следующем: перебирая числа k из диапазона от 2 до n − 1 , будем делить n на k с остатком. Если при каком-то k обнаружится нулевой остаток, значит, n делится на k нацело, и число n составное. Если же при делении обнаруживались только ненулевые остатки, значит, число простое; в этом случае выводим его на экран. Ясно, что, получив нулевой остаток (тем самым обнаружив, что n составное), следует отказаться от дальнейших проб на делимость.

Заметим, что все простые числа, за исключением двойки, нечётные. Если обработать особо случай n = 2 , то все последующие числа n можно перебирать с шагом 2 . Это даст приблизительно двукратное увеличение производительности программы.

Оптимизированный перебор делителей

Ещё одно улучшение возникает благодаря следующему утверждению: наименьший делитель составного числа n не превосходит n . Докажем это утверждение от противного. Пускай число k является наименьшим делителем n , причём k > n . Тогда n = k ⁢ l , где l ∈ ℕ , причём l ⩽ n , то есть l также является делителем числа n , кроме того, меньшим, чем k , а это противоречит предположению. Всё это означает, что, перебирая потенциальные делители, можно оборвать перебор, когда k достигнет n : если до этого момента делителей не найдено, то их нет вообще. Кстати, при проверке на простоту числа 11 это наблюдение позволяет сократить перебор более чем в три раза, а для числа 1111111111111111111 — более чем в 1054092553 раза (оба числа — простые).

Перебор с запоминанием найденных простых чисел

Существенно сократить перебор возможных делителей можно, пожертвовав памятью во время исполнения программы. В основе этой оптимизации лежит следующее утверждение: наименьший собственный делитель k составного числа n (то есть отличный от единицы и от самого n ) является простым. Докажите самостоятельно.

Поскольку при проверке числа n на простоту важен именно наименьший собственный делитель, делители следует искать среди простых чисел, перебирая их по порядку. Но где взять их список? Ответ прост: поскольку наша программа будет искать все простые числа по порядку, кроме вывода на экран будем добавлять их в список найденных простых. Для очередного n будем перебирать потенциальные делители только из этого списка, по-прежнему, вплоть до n .

Издержкой этого подхода является необходимость держать в памяти растущий список найденных простых чисел. Однако объём требуемой для этого памяти будет невелик по сравнению с громадным выигрышем в быстродействии. Следующая таблица даёт представление об экономии при переборе и о затратах памяти:

n количество k ⩽ n количество простых k ⩽ n
10 3 1
100 10 4
1000 31 10
10000 100 25
100000 316 65
1000000 1000 168

Решето Эратосфена

Другой алгоритм поиска простых чисел приписывают древнегреческому учёному Эратосфену Киренскому (Έρατοσθένης).

Обратите внимание: количество зачёркиваний у составного числа — это количество простых делителей (без учёта кратности).

Колёсный метод

Трюк, упомянутый в разделе «Наивный перебор», позволяет вдвое сократить список кандидатов в простые числа — заведомо составными будут все чётные числа кроме двойки. Посмотрим, нельзя ли подобным образом учесть ещё несколько первых простых чисел, чтобы дополнительно уменьшить число кандидатов.

Чисел, делящихся на 2 — половина, а делящихся на 3 — треть. Значит, доля чисел, делящихся хотя бы на одно из этих чисел, равна 1 2 + 1 3 − 1 2 ⋅ 1 3 = 2 3 (вычитается доля чисел, делящихся и на 2 , и на 3 , иначе такие числа будут учтены дважды). Для интересной операции, которую мы только что выполнили над дробями 1 2 и 1 3 , введём обозначение: x ⊕ y = x + y − x ⁢ y .

Очевидно, операция ⊕ коммутативна: x ⊕ y = y ⊕ x . Кроме того, как нетрудно проверить, она ассоциативна: x ⊕ y ⊕ z = x ⊕ y ⊕ z .

Теперь ясно, что учёт следующего простого числа, пятёрки, увеличивает долю заведомо составных чисел (делящихся на 2 , 3 , 5 ) до 1 2 ⊕ 1 3 ⊕ 1 5 = 11 15 . Учёт семёрки даст 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ 1 7 = 11 15 ⊕ 1 7 = 27 35 . Интересно выяснить, какую выгоду можно получить, учитывая следующие простые числа, и каковы будут издержки.

Мы вычислили «суммы» обратных величин для первых k простых чисел и свели результаты в таблицу:

k 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ … ⊕ 1 p k
1 0,5000…
2 0,6667…
3 0,7333…
4 0,7714…
5 0,7922…
6 0,8082…
7 0,8195…
8 0,8290…
9 0,8364…
10 0,8421…

Числа в правой колонке таблицы растут, но всё медленней.

Список чисел от 1 до P k , взаимно простых с P k , назовём колесом, а сами такие числа — спицами в колесе. Теперь мы знаем, что любое из простых чисел либо одно из p 1 , p 2 , … , p k , либо содержится среди чисел вида s + n ⁢ P k , где s — спица. Все остальные натуральные числа, кроме единицы, заведомо составные, и их доля, как показывает таблица, довольно велика даже для небольших k .

Для проверки числа N на простоту следует прежде всего поискать N среди чисел p 1 , p 2 , … , p k . Если поиск не увенчался успехом, проверяем по очереди, не делится ли N на одно из p i . Если делится, число N — составное. Если же нет, ищем делители N среди спиц колеса s (пропустив, естественно, единицу), затем среди чисел вида s + P k , затем среди чисел вида s + 2 ⁢ P k , затем — s + 3 ⁢ P k , и так продолжаем до тех пор, пока квадрат очередного делителя не превысит N .

Построим колёса для первого одного простого числа, первых двух и первых трёх:

k колесо
1 1
2 1 , 5
3 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29
4 1 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 121 , 127 , 131 , 137 , 139 , 143 , 149 , 151 , 157 , 163 , 167 , 169 , 173 , 179 , 181 , 187 , 191 , 193 , 197 , 199 , 209

Возьмём для примера колесо, построенное для двух первых простых чисел — 2 и 3 . Проверяя на простоту число N при помощи такого колеса, убедившись, что N не двойка и не тройка, пытаемся делить это число сначала на 2 , 3 , а затем — на 5 , 7 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , … , то есть на числа из арифметических прогрессий 1 + 6 ⁢ t и 5 + 6 ⁢ t , t = 0 1 2 3 … . При N = 661 имеет смысл остановиться на числе 25 , поскольку квадрат следующего в списке, 29 , уже больше 661 . Теперь можно заключить, что число 661 — простое.

Удобно изображать список возможных делителей в виде таблицы шириной P k (в нашем примере это 2 ⋅ 3 = 6 ): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 … Серые числа заведомо составные. Среди цветных чисел также могут встретиться, хоть и редко, составные числа (синие) — мы помним, что колёсный метод исключает не все составные числа из рассмотрения.

Для проверки того же числа 661 на колесе, построенном для трёх первых простых чисел, нужно проверить его делимость сначала на 2 , 3 , 5 , затем — на 7 , 11 , 13 , 17 , 19 , 23 .

Есть соблазн использовать для построения колеса как можно больше первых простых чисел. Но не стоит этого делать. Выигрыш с добавлением очередного простого числа будет всё меньше и меньше, а количество спиц в k -ом колесе будет расти всё быстрее и быстрее. Можно показать, что количество спиц в k -ом колесе равно p 1 − 1 ⁢ p 2 − 1 ⁢ p 3 − 1 ⋅ … ⋅ p k − 1 . Эта последовательность выглядит так: 1 , 2 , 8 , 48 , 480 , 5760 , 92160 , 1658880 , … . Слишком большие колёса только замедлят выполнение программы, к тому же создание списка спиц потребует массу времени. Наши эксперименты показали, что оптимальное количество простых, используемых для построения колеса, равно четырём.

Ах, да. Почему метод называется колёсным? Возьмём колесо со спицами, пронумерованными от 1 до P k , и удалим спицы с номерами, не взаимно простыми с P k . Если прокатить такое колесо по прямой, отмечая следы концов уцелевших спиц, на прямой останутся отметки, принадлежащие арифметическим прогрессиям вида s + P k ⁢ t . Первые три колеса показаны на рисунке 14.1. «Колёса для проверки чисел на простоту». Следующее колесо уже в семь раз больше самого крупного из показанных, и мы решили воздержаться от его рисования.

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

В процессе обучения программированию я столкнулся с задачей поиска 1M первых простых чисел.

На Хабре уже не раз писали об этом. Но, чаще всего, речь шла о поиске всех простых чисел до числа N. Я же расскажу о том, как решал задачу нахождения N первых простых чисел.

На первый взгляд может показаться, что разницы в этих задачах практически нет. И это действительно так, пока мы не поймем, что перебор делителей справляется с задачей крайне плохо.

В результате проведенной работы на поиск 1 миллиона простых чисел у меня уходит всего 0,262 секунды, что, конечно же, не предел, но уже впечатляет. Алгоритм реализован на C++.

Как и автор предыдущей статьи о простых числах, я начал решать задачу лоб в лоб. Итак, простое число p — то, что имеет два делителя — единицу и p. Первое, что приходит в голову — проверять каждое число делением на все предыдущие числа.

Идея, как оказалось, плохая. Понял я это после первых 30 минут работы программы в поисках миллиона простых. Результаты получились такие:

10 000 — 2,349 с.
100 000 — 293,552 с.
1 000 000 — не дождался

Как и в уже упомянутой выше статье я принялся за оптимизацию алгоритма. Во-первых, проверять четные числа не имеет смысла, ведь 2 — единственное простое четное число. То же самое с делителями — на четные можно не проверять. В-третьих, в качестве делителей достаточно брать числа не превышающие половину проверяемого числа. Вот, что из этого вышло:

Стало лучше, но миллиона я так и не смог дождаться
10 000 — 0,589 с.
100 000 — 72,662 с.
1 000 000 — после 20 минут ждать перестал

Понятно, что продолжать оптимизировать этот алгоритм можно еще долго, чем я в общем-то и занимался. Можно не проверять числа заканчивающиеся на 5 и 0. Можно составить список самых распространенных делителей и проверять каждое число сначала на них. В какой-то момент мне показалось, что я смогу решить проблему, проверяя новые числа только на уже найденные простые. Значительных результатов это не принесло. Проблема крылась в том, что с каждым новым числом, количество проверок возрастало, да и операция деления — одна из самых тяжелых.

Отправился в поиск. Узнал про решето Эратосфена. Но использовать алгоритм в том виде, как он есть для моей задачи нельзя. Заранее ведь неизвестно*, сколько надо просеять чисел, чтобы найти N простых. Поэтому я решил модифицировать алгоритм под свои нужды следующим образом.

Просеивать заранее большой набор натуральных чисел не выгодно. Значит надо просеивать некоторые наборы натуральных чисел до тех пор, пока не достигнем нужного результата. Причем каждый новый набор надо сначала просеять на уже найденные простые числа. Вот код, полученный уже после ряда оптимизаций:

// Listing 2

#include

#include

#include

using namespace std ;

int main ( )

< clock_t start = clock ( ) ; const int AIM = 1000000 ; int startSize = AIM ; // стартовый размер массива натуральных чисел int addSize = AIM ; // размер дополнительного массива натуральных чисел vector < bool >nums ( startSize ) ;

vector < int >primeNums ( AIM ) ;

int foundPrimes = 0 ;

for ( int i = 2 ; i < startSize ; i ++ ) nums [ i ] = true ; bool addition = false ; int adder = 0 ; while ( true ) < if ( addition ) < nums. resize ( nums. size ( ) + addSize, true ) ; // исключим составные числа простыми из предыдущих итераций for ( int i = 0 ; i < foundPrimes ; i ++ ) < int cur_num = primeNums [ i ] ; if ( ( addSize + ( ( nums. size ( ) — addSize ) % cur_num ) ) < cur_num ) continue ; for ( int j = ( ( nums. size ( ) — addSize ) / cur_num ) * cur_num ; j < nums. size ( ) ; j + = cur_num ) nums [ j ] = false ; >

>

else

addition = true ;

int iter ;

if ( foundPrimes == 0 )

iter = 2 ;

else

iter = primeNums [ foundPrimes — 1 ] + 2 ;

for ( ; iter < nums. size ( ) ; iter ++ ) < // выбираем очередное простое число if ( nums [ iter ] ) < primeNums [ foundPrimes ] = iter ; foundPrimes ++ ; if ( foundPrimes == AIM ) break ; // просеиваем for ( int j = iter + iter ; j < nums. size ( ) ; j + = iter ) nums [ j ] = false ; >

else

continue ;

>

if ( foundPrimes == AIM )

break ;

>

cout

clock_t end = clock ( ) ;

cout
cout
return 0 ;

>

Результаты даже слегка удивили:
10 000 — 0,001 с.
100 000 — 0,021 с.
1 000 000 — 0,262 с.

10 000 000 — 2,999 с.

На этом с задачей поиска 1M первых простых чисел я закончил. Результат меня вполне удовлетворил. Но что можно сделать ещё? Можно реализовать какой-нибудь из известных алгоритмов на основе решета Эратосфена, например, решето Сундарама. Но вряд ли результаты изменяться значительно. Возможно, решето Аткина сможет показать себя лучше — именно этот алгоритм чаще всего используется в современной криптографии.

* — неизвестно мне. halyavin рассказал в первом комментарии, что оказывается давно известно.

UPD
Относительно потребления памяти, описанные алгоритмы ведут себя следующим образом:

1 млн. простых чисел, максимальное ОЗУ
— перебор делителей: ~4Мб
— модифицированное решето Эратосфена: ~6Мб

10 млн. простых чисел, максимальное ОЗУ
— перебор делителей: ~39Мб
— модифицированное решето Эратосфена: ~61Мб

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *