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

алгебра — Определить кол-во простых чисел от 1 до n с математической точки зрения

Здравствуйте. Как определить кол-во простых чисел от 1 до n с математической точки зрения, например от 1 до 10^9.

задан 18 Янв ’14 0:26

Чтобы найти точно это количество, нужно всё «честно» подсчитать — «обходных» способов тут нет. Но для приблизительной оценки существует асимптотический закон распределения простых чисел. В отрезке от $%1$% до $%n$% таких чисел имеется порядка $%\frac<\ln n>$%. При $%x\to\infty$% отношение числа $%\pi(x)$% (так стандартно обозначается количество простых чисел, не превосходящих $%x$%) к величине $%x/\ln x$% стремится к единице.

Я не до конца понимаю постановку задачи. В частности, мне не ясна роль параметра $%k$%. Что он означает? Хотелось бы «чистого» описания на математическом языке, без «занимательного» сюжета и персонажей (мне трудно отсеивать ненужную информацию). Скорее всего, тут должно работать решето Эратосфена. Более сложных средств в такого рода задачах, как правило, не используется.

Число является простым если оно не делится от 2 до k+1,решето Эратосфена здесь не подходит

Falcao,отвечаю про k. В условии задачи сказано, что год не должен быть простым, а он должен казаться главному герою простым, то есть не иметь простых делителей меньших k+2.Решето Эратосфена в этой задаче здесь не подходит,а вот как в этой задаче можно использовать метод включений-исключений на отрезке с учетом k

@ivan145: роль числа $%k$% я теперь понял. Решето Эратосфена, если я правильно понимаю, не подходит по той причине, что в худшем случае оно требует прохождения массива длиной $%10^9$%, а это считается много. Если это в самом деле так, то напрашивается идея использования формулы включений и исключений. Реализовать её, судя по всему, можно. Я попробую тогда изложить свои соображения.

Отвечаю здесь, так как снизу всё исчерпано. Конечно, никаких произведений порядка $%10^<18>$% здесь в принципе возникнуть не может. Ведь рассматриваются только числа до $%10^9$%, и у них не бывает столь огромных делителей. Я уже говорил, что задача подсчёта для $%[A;B]$% сводится к нахождению разности $%f(B)-f(A-1)$%, то есть параметр в задаче фактически один: число $%n$% от $%1$% до $%10^9$%, для которого мы ищем $%f(n)$%.

Falcao,я все реализовал,не считал те произведения которые больше 2*10^9,на тестах где k маленькое все проходит довольно неплохо,но в худшем случае при k=300,считает 3 секунды.Не может ли у этой задачи быть другого решения?

2 ответа

Попробую изложить реализацию одного из алгоритмов. Задачу я понимаю так. Нам даны три числа: $%A$%, $%B$% и $%k$%. Требуется найти количество чисел отрезка $%[A;B]$%, которые не делятся ни на одно простое число из отрезка $%[2;k+1]$%. Поскольку $%k$% сравнительно небольшое, мы можем быстро выписать все такие числа, пользуясь решетом Эратосфена. В худшем случае возникает список 2, 3, 5, . 293, в который входят 62 простых числа. Теперь надо реализовать функцию $%f(n)$%, которая подсчитывает количество чисел отрезка $%[1;n]$%, не делящихся ни на одно из указанных. Это будет некая процедура-функция, и далее она дважды вызывается, и вычисляется разность $%f(B)-f(A-1)$%. Число $%n$% может иметь порядок $%10^9$%.

Для подсчёта $%f(n)$% нужно узнать количество чисел, делящихся хотя бы на одно из наших простых. Пусть эти простые числа суть $%p_1 < \cdots < p_m$%. Количество чисел отрезка $%[1;n]$%, делящихся на $%p_i$%, нам известно, и оно вычисляется по формуле $%[n/p_i]$%, где квадратные скобки обозначают целую часть. В соответствии с формулой включений и исключений, все эти числа складываются. Далее из них надо вычесть величины, соответствующие попарным пересечениям, то есть $%[n/(p_ip_j)]$% при $%i < j$%. Потом прибавляются числа для тройных пересечений, и так далее.

Проблема в том, что пересечений, вообще говоря, имеется очень много, и в общем случае это будет величина порядка $%2^<62>$% (каждое простое число можно брать или не брать, составляя произведение различных простых). Однако у нас тут имеется ограничение чисел по величине, поэтому брать те произведения простых, которые превышают $%10^9$%, нам уже не надо. Соответственно, задача сводится к нахождению эффективного принципа перебора всех произведений различных простых из списка $%p_1,\ldots p_m$%, с условием, что произведение не превышает $%10^9$%.

Сделаем ещё вот какое замечание. Если нам надо подсчитать число $%[n/(st)]$%, то можно это сделать по формуле $%[[n/s]/t]$%, то есть округлять можно после каждого деления. Тогда составляем список чисел $%[n/p_1],[n/p_2],\ldots,[n/p_m]$%. Все эти числа складываем. Про каждое число мы запоминаем, на какое $%p_i$% мы его последний раз делили. Далее $%[n/p_1]$% делим с округлением на числа $%p_2,\ldots,p_m$%; число $%[n/p_2]$% делим с округлением на более «поздние» числа $%p_3,\ldots,p_m$% и так далее; $%[n/p_]$% делим с округлением на $%p_m$%. Все полученные числа вычитаются. И далее повторяем эту процедуру, на каждом шаге меняя вычитание на сложение и наоборот, пока не произойдёт обнуление. Надо заметить, что количество действий тут не должно быть слишком большим: произведение первых 10 простых чисел уже превышает $%10^9$%, то есть делить слишком много раз будет не нужно. У самых больших простых чисел списка вообще берутся только три сомножителя. Судя по всему, этот план должен быть реализуем за предлагаемое время.

отвечен 18 Янв ’14 22:47

@falcao Думаю, что предложенное Вами решение действительно может уложится в ограничение времени. Но «Это будет некая процедура-функция, и далее она дважды вызывается, и вычисляется разность f(B)−f(A−1). Число n может иметь порядок $$10^9$$.» В случае если А и В будут достаточно большими числами, а их разность небольшой, например, А=999999995 и В=999999999, то вместо проверки 4 чисел будут необоснованно дважды вычисляться значения функции для достаточно больших чисел. Уверен, что несколько тестов будут именно такого плана.

Falcao,понял все до замечания.Является ли замечание еще одним способом решения задачи?или это продолжение того,что вы написали ранее?можно поконкретней о чем говорится в замечании.

@aid78: с Вашим замечанием я согласен. Но дело в том, что такого рода соображений может быть много, и они играют роль уже на стадии реализации программы. Она может себя вести как-то по-особому при «малых» значениях $%B$%, или $%B-A$%. У меня в первую очередь речь шла о преодолении чисто математических трудностей для «худшего» случая.

@ivan145: замечание касалось способа вычисления целой части. Вместо $%[n/6]$% можно брать подсчитанное ранее значение $%[n/2]$%, которое далее делим на 3 с округлением вниз и получаем то же самое. Так удобнее реализовать алгоритм. Дальше у меня шло описание основной части, с формулой включений и исключений. Его было бы уместно начать с новой строки, так как это отдельная мысль, хотя и связанная с предыдущей. Фактически, это основной момент в вычислениях. Представьте себе формулу типа $%[n/p_1]+\ldots+[n/p_m]-([n/(p_1p_2]+[n/(p_1p_3)]+\ldots)+([n/(p_1p_2p_3)+\ldots)-$% и далее по тексту.

Ага,это и есть формула включений и исключений,и вы говорите,что здесь можно сделать отсечение,что если произведение превысит 10^9,то уже это необязательно рассматривать.А почему это необязательно рассматривать?и не нарушит ли это итоговый ответ?

@ivan145: представьте себе формулу включений и исключений для этого случая в её полном виде. Если мы поделили $%n$% на очень большое число, то целая часть такого частного равна нулю. Поэтому слагаемые этого вида можно не рассматривать. Мы ведь по формуле $%[n/s]$% подсчитываем количество чисел от 1 до $%n$%, кратных $%s$%, но в случае $%s > 10^9$% таких чисел просто нет.

Да с таким отсечением согласен,но есть проблема.Допустим нам достался худший случай и чисел простых будет 62.И когда (n/(p1p2p3p4p5p6p7p8p9p10)+n/(p1p2p3p4p5p6p7p8p9p11))и т.д. в фор-ле включений и исключений то этот перебор комбинаций займет слишком много времени,если составлять комбинации по 2,3,4,5 то это еще проходит,возможно пройдет и по 6,но когда составляем комбинации из 62 чисел по семь,то тут уже начинаются проблемы.Возможно ли это как-то избежать?

@ivan145: здесь не надо составлять все комбинации (сочетания) из 62 по 7. Учитывать и рассматривать надо только те произведения простых, которые не превосходят $%10^9$%. Их относительно немного, и «отсев» происходит на достаточно ранней стадии. Я показал, как можно осуществить перебор при помощи составления списков. Об этом в последнем абзаце говорится. Суть в том, что «длинных» произведений в списке будет очень мало.

Ага,понял,и еще кое-что по условию задачи a<=10^9 и b<=10^9 а это означает рассматривать надо только те произведения простых которые не превосходят 10^18 или я не прав?

В условии задачи сказано, что год не должен быть простым, а он должен казаться главному герою простым, то есть не иметь простых делителей меньших k+2. Решето Эратосфена от 2 до k+1 здесь должно подойти. Его реализацию на любом распространенном алгоритмическом языке не сложно найти с сети. А если будет лимит времени, то сделайте отдельную программу, которая будет заполнять массив логических переменных от 1 до 10^9 по принципу true если число не имеет делителей меньших k+2 и false в противном случае. В ту программу, что будете тестировать внесите этот массив как массив констант и в самой программе считайте сколько true попало от A до B.

отвечен 18 Янв ’14 10:00

Извините,но я уже это пробывал,слишком много памяти выделяется,поэтому этот вариант отпадает

@ivan145: приходится отвечать здесь. Я посмотрел в условие, и там, насколько я понимаю, $%B$% играет роль количества чисел отрезка, то есть найти надо то, что попадает в $%[A;A+B]$%. Сути дела это не меняет, так как слегка изменяется ограничение: получается $%2\cdot10^9$%, то есть величина того же порядка, что и была. Разумеется, никакого $%10^<18>$% тут нет и быть не может: ведь числа $%A$% и $%B$% всего лишь складываются, а не перемножаются.

@ivan145: я говорил, что не надо считать через $%C_<62>^7$%. Ясно, что это очень большое число (порядка половины миллиарда). У меня был описан другой алгоритм, основанный на составлении списков. Я могу попробовать сегодня вечером его реализовать в Maple чисто ради спортивного интереса. Вариантов там не должно быть слишком много.

@ivan145: я пришёл к этому выводу на основании того, какие именно члены надо учитывать в формуле включений и исключений. Они именно такие, как я описал. Понятно, что каждое из них учитывать нужно в силу вида формулы. То есть надо работать со списками, учитывая то, на что мы уже делили, чтобы не повторить дважды то же самое. А привлекать сочетания тут незачем, потому что очень многие произведения 7 сомножителей слишком велики. Кроме того, сам алгоритм перебора сочетаний, если его реализовать, превратится примерно в то же самое.

Насколько я понимаю,это почти тоже самое,что и перебор сочетаний,но убыстренный в силу того,что мы запоминаем предущие вычисления

@ivan145: я делаю похоже, но немного не так. На каждом шаге мы храним списки чисел. На нулевом шаге есть список из числа n. Скажем, что оно имеет ранг 0. Это число идёт с плюсом при вычислении ответа. Далее возникает m списков из одного числа каждый: $%n/p_1$%; . ; $%n/p_m$%. Этим числам присваиваем ранги от 1 до m. Это всё идёт с минусом. На следующем шаге возникают списки: $%n/(p_1p_2)$% (ранг 2), $%n/(p_1p_3)$%, $%n/(p_2p_3)$% (ранг 3), . $%n/(p_1p_m)$%, . $%n/(p_p_m)$% (ранг m). Знаки всё время меняются; рангом считается наибольший номер i, если делили на $%p_i$%.

для n/(pm-1pm) понятно как будет выглядеть алгоритм,а как он будет выглядеть когда делим n на три элемента?И как мы эти числа все время будем запоминать с этим тоже проблема,ведь их становится все больше и больше

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Существует ли формула для определения кол-ва простых чисел?

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

— Вс авг 16, 2009 02:04:08 —

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

Если через $» /> обозначить количество натуральных чисел, взаимнопростых с числом , непревышающих , то количество простых чисел, непревышающих , можно точно подсчитать по бесконечной формуле:

— простые числа 2, 3, 5, 7. непревышающие равно , это будет «формулой» или нет?

Просто я пытался вывести формулу и она у меня получилась. Стал искать подобную формулу в интернете, нашёл различные формулы, но точно такую же, как и у меня не нашёл.
Вот она:— это количество простых чисел от 1 до N.

Что это за формула? Наверняка, её вывели лет 150-200 назад. Дайте, пожалуйста, ссылки на сайты, где она упомянута.
Можно ли считать эту формулу тривиальной?

И ещё вопрос, как поставить знак праймориал «#» в коде math?

— Пн авг 17, 2009 16:42:24 —

Батороев
Мне кажется, что формула, написанная мной выше, куда более проста и эффективна,чем упомянутая вами Или же я всё-таки ошибаюсь?

Профессор Снэйп
«Бесконечная формула» — это я сказал детским, «школьным» языком, дабы сам в этом году только окончил 11 класс

Вот она:— это количество простых чисел от 1 до N.
Что это за формула? Наверняка, её вывели лет 150-200 назад. Дайте, пожалуйста, ссылки на сайты, где она упомянута.
В очень старом «Кванте»(60е-70е гг)была такая:
Ваша формула даст ( ), если я правильно понял Ваши обозначения, конечно.

P.P.S. То есть у Вас в знаменателе праймориал? А для его вычисления Вам же нужно будет знать те же N простых чисел, что является более сложной задачей, разве нет?

Формулу необходимо подкорректировать.
Правильнее будет так:
— количество простых чисел от 1 до N;
— целая часть числа ;
— праймориал, то есть произведение простых чисел от 1 до ()

Важное замечание.
— это именно целая часть числа , а не округление числа .
То есть — наибольшее простое, не превышающее (если речь идет о точной формуле расчета количества простых).
Заодно спрошу, какой ответ получается по Вашей формуле для ?
Я тут проверил, формула начинает превышать правильное количество простых чисел при , и это расхождение постепенно увеличивается, при расхождение составляет , при — .
Cкачки происходят при . Видимо, Вы в доказательстве где-то не учитываете степени простых чисел и произведения простых чисел, идущих не подряд.

Теория чисел

Простым называется натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается. Составным числом называют непростое число, которое еще и не единица.

Примеры простых чисел: \(2\) , \(3\) , \(5\) , \(179\) , \(10^9+7\) , \(10^9+9\) .

Примеры составных чисел: \(4\) , \(15\) , \(2^<30>\) .

Еще одно определение простого числа: \(N\) — простое, если у \(N\) ровно два делителя. Эти делители при этом равны \(1\) и \(N\) .

Проверка на простоту за линию

С точки зрения программирования интересно научиться проверять, является ли число \(N\) простым. Это очень легко сделать за \(O(N)\) — нужно просто проверить, делится ли оно хотя бы на одно из чисел \(2, 3, 4, \ldots, N-1\) . \(N > 1\) является простым только в случае, если оно не делится на на одно из этих чисел.

Проверка на простоту за корень

Алгоритм можно ускорить с \(O(N)\) до \(O(\sqrt)\) .

Пусть \(N = a \times b\) , причем \(a \leq b\) . Тогда заметим, что \(a \leq \sqrt N \leq b\) .

Почему? Потому что если \(a \leq b < \sqrt\) , то \(ab \leq b^2 < N\) , но \(ab = N\) . А если \(\sqrt < a \leq b\) , то \(N < a^2 \leq ab\) , но \(ab = N\) .

Иными словами, если число \(N\) равно произведению двух других, то одно из них не больше корня из \(N\) , а другое не меньше корня из \(N\) .

Из этого следует, что если число \(N\) не делится ни на одно из чисел \(2, 3, 4, \ldots, \lfloor\sqrt\rfloor\) , то оно не делится и ни на одно из чисел \(\lceil\sqrt\rceil + 1, \ldots, N-2, N-1\) , так как если есть делитель больше корня (не равный \(N\) ), то есть делитель и меньше корня (не равный 1). Поэтому в цикле for достаточно проверять числа не до \(N\) , а до корня.

Разложение на простые множители

Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.

\[11 = 11 = 11^1\] \[100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2\] \[126 = 2 \times 3 \times 3 \times 7 = 2^1 \times 3^2 \times 7^1\]

Рассмотрим, например, такую задачу:

Условие: Нужно разбить \(N\) людей на группы равного размера. Нам интересно, какие размеры это могут быть.

Решение: По сути нас просят найти число делителей \(N\) . Нужно посмотреть на разложение числа \(N\) на простые множители, в общем виде оно выглядит так:

\[N= p_1^ \times p_2^ \times \ldots \times p_k^\]

Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень \(i\) -го простого число от 0 до \(a_i\) (то есть \(a_i+1\) различное значение), и так для каждого. То есть делитель \(N\) выглядит ровно так: \[M= p_1^ \times p_2^ \times \ldots \times p_k^, 0 \leq b_i \leq a_i\] Значит, ответом будет произведение \((a_1+1) \times (a_2+1) \times \ldots \times (a_k + 1)\) .

Алгоритм разложения на простые множители

Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа \(N\) , мы можем число \(N\) на него поделить и продолжить искать новый минимальный простой делитель.

Будем перебирать простой делитель от \(2\) до корня из \(N\) (как и раньше), но в случае, если \(N\) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз ( \(N\) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда \(N\) стало либо \(1\) , либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само \(N\) добавить в ответ.

Напишем алгоритм факторизации:

Задание

За сколько работает этот алгоритм?

Решение

За те же самые \(O(\sqrt)\) . Итераций цикла while с перебором делителя будет не больше, чем \(\sqrt\) . Причем ровно \(\sqrt\) операций будет только в том случае, если \(N\) — простое.

А итераций деления \(N\) на делители будет столько, сколько всего простых чисел в факторизации числа \(N\) . Понятно, что это не больше, чем \(O(\log)\) .

Задание

Докажите, что число \(N\) имеет не больше, чем \(O(\log)\) простых множителей в факторизации.

Разные свойства простых чисел*

Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:

• Простых чисел, меньших \(N\) , примерно \(\frac<\ln N>\) .
• N-ое простое число равно примерно \(N\ln N\) .
• Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
• Для любого \(N \ge 2\) на интервале \((N, 2N)\) всегда найдется простое число (Постулат Бертрана)
• Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с \(N! + 2\) .
• Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень. равно примерно \(O(\sqrt[3])\) . Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
• Максимальное число делителей у числа на отрезке \([1, 10^5]\) — 128
• Максимальное число делителей у числа на отрекзке \([1, 10^9]\) — 1344
• Максимальное число делителей у числа на отрезке \([1, 10^<18>]\) — 103680
• Наука умеет факторизовать числа за \(O(\sqrt[4])\) , но об этом как-нибудь в другой раз.
• Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.

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

Часто нужно не проверять на простоту одно число, а найти все простые числа до \(N\) . В этом случае наивный алгоритм будет работать за \(O(N\sqrt N)\) , так как нужно проверить на простоту каждое число от 1 до \(N\) .

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до \(N\) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Задание

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

У этого алгоритма можно сразу заметить несколько ускорений.

Во-первых, число \(i\) имеет смысл перебирать только до корня из \(N\) , потому что при зачеркивании составных чисел, делящихся на простое \(i > \sqrt N\) , мы ничего не зачеркнем. Почему? Пусть существует составное \(M \leq N\) , которое делится на %i%, и мы его не зачеркнули. Но тогда \(i > \sqrt N \geq \sqrt M\) , а значит по ранее нами доказанному утверждению \(M\) должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.

Во-вторых, по этой же самое причине \(j\) имеет смысл перебирать только начиная с \(i^2\) . Зачем вычеркивать \(2i\) , \(3i\) , \(4i\) , …, \((i-1)i\) , если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на \(2\) , \(3\) , \(4\) , …, \((i-1)\) .

Асимптотика

Такой код будет работать за \(O(N \log \log N)\) по причинам, которые мы пока не хотим объяснять формально.

Гармонический ряд

Научимся оценивать асимптотику величины \(1 + \frac<1> <2>+ \ldots + \frac<1>\) , которая нередко встречается в задачах, где фигурирует делимость.

Возьмем \(N\) равное \(2^i — 1\) и запишем нашу сумму следующим образом: \[\left(\frac<1><1>\right) + \left(\frac<1> <2>+ \frac<1><3>\right) + \left(\frac<1> <4>+ \ldots + \frac<1><7>\right) + \ldots + \left(\frac<1><2^> + \ldots + \frac<1><2^i - 1>\right)\]