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

[Rasulka]

Много раз уже встречал формулы, по которым можно лишь приближенно оценить количество простых чисел от 1 до N. У меня возник вопрос, существует ли формула для нахождения точного количества простых чисел от 1 до N, пусть даже эта формула будет бесконечной?

[maxmatem]

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

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

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

[age]

Да, но науке она не известна, т.к. она действительно зависит от порядка числа на числовой оси: чем оно больше, тем и формула сложнее.

[Xaositect]

Rasulka в сообщении #235461 писал(а):

Много раз уже встречал формулы, по которым можно лишь приближенно оценить количество простых чисел от 1 до N. У меня возник вопрос, существует ли формула для нахождения точного количества простых чисел от 1 до N, пусть даже эта формула будет бесконечной?

В корневом разделе такая тема есть: topic21405.html

[Батороев]

Если через $ \varphi{(s; m)} $ обозначить количество натуральных чисел, взаимнопростых с числом $ s $, непревышающих $ m $, то количество простых чисел, непревышающих $ N $, можно точно подсчитать по бесконечной формуле:

$ \pi(N) = \dfrac{N}{2} + (i - 1) - \varphi(p_1; \dfrac{N}{p_2}) - \varphi((p_1\cdot p_2); \dfrac{N}{p_3}) - ... - \varphi((p_1\cdot p_2\cdot...\cdot p_{i-1}); \dfrac{N}{p_i}) $,

где $ p_1, p_2, p_3, p_4... p_i $ - простые числа 2, 3, 5, 7..., непревышающие $ \sqrt {N} $.

-- Вс авг 16, 2009 12:58:00 --

maxal в сообщении #92335 писал(а):

Это формула Лежандра.

[Профессор Снэйп]

Rasulka в сообщении #235461 писал(а):

...формула для нахождения точного количества простых чисел от 1 до N, пусть даже эта формула будет бесконечной?

Бесконечных формул не бывает

Думаю, для начала стоит определиться с тем, что такое "формула". Вот если я напишу, что количество простых чисел в промежутке $[1,N]$ равно $\pi(N)$, это будет "формулой" или нет?

[Rasulka]

Просто я пытался вывести формулу и она у меня получилась. Стал искать подобную формулу в интернете, нашёл различные формулы, но точно такую же, как и у меня не нашёл.
Вот она:$\pi(N) = [N]-[\dfrac{N-2}{2}]-[\dfrac{N-3}{2*3}]-[\dfrac{N-5}{2*3*5}]-[\dfrac{N-7}{2*3*5*7}]...$

Где $\pi(N)$ - это количество простых чисел от 1 до N.

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

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

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

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

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

[nn910]

Rasulka в сообщении #235877 писал(а):

Вот она:$\pi(N) = [N]-[\dfrac{N-2}{2}]-[\dfrac{N-3}{2*3}]-[\dfrac{N-5}{2*3*5}]-[\dfrac{N-7}{2*3*5*7}]...$
Где $\pi(N)$ - это количество простых чисел от 1 до N.
Что это за формула? Наверняка, её вывели лет 150-200 назад. Дайте, пожалуйста, ссылки на сайты, где она упомянута.

В очень старом "Кванте"(60е-70е гг)была такая:
$\pi(N) = N-[\dfrac{N}{2}]-[\dfrac{N}{3}]+[\dfrac{N}{2*3}]-[\dfrac{N}{5}]+[\dfrac{N}{2*5}]+[\dfrac{N}{3*5}]-[\dfrac{N}{2*3*5}]...$
Только статья даже не на тему"К-во простых" а про "Формулу включений и исключений"

[JollyRoger]

Rasulka в сообщении #235461 писал(а):

У меня возник вопрос, существует ли формула для нахождения точного количества простых чисел

Rasulka в сообщении #235877 писал(а):

Просто я пытался вывести формулу и она у меня получилась. Стал искать подобную формулу в интернете, нашёл различные формулы, но точно такую же, как и у меня не нашёл.
Вот она:$\pi(N) = [N]-[\dfrac{N-2}{2}]-[\dfrac{N-3}{2*3}]-[\dfrac{N-5}{2*3*5}]-[\dfrac{N-7}{2*3*5*7}]...$

Вы считаете Ваша формула даёт точное количество простых чисел? Как её выводили, кстати?

[Rasulka]

Цитата:

Вы считаете Ваша формула даёт точное количество простых чисел?

Да, её я проверял и не один раз. А что, есть какие-то сомнения по поводу её правильности?

Цитата:

Как её выводили, кстати?

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

[JollyRoger]

Rasulka в сообщении #235888 писал(а):

Да, её я проверял и не один раз. А что, есть какие-то сомнения по поводу её правильности?

Например, при $ N = 4 $ Ваша формула даст $4$ ( $ 4 - 1 - 0 + 1 $ ), если я правильно понял Ваши обозначения, конечно.

P.S.

Rasulka в сообщении #235877 писал(а):

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

$ \sharp,\ \# $

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

[Rasulka]

Формулу необходимо подкорректировать.
Правильнее будет так:
$\pi(N) = [N]-[\dfrac{N-2}{2\#}]-[\dfrac{N-3}{3\#}]-[\dfrac{N-5}{5\#}]-[\dfrac{N-7}{7\#}]...-1$

То есть в конце необходимо вычесть 1, так как 1 - это не простое число. Поэтому в конце в формулу нужно добавить "-1".
Обозначения:
$\pi(N)$ - количество простых чисел от 1 до N;
$[x]$ - целая часть числа $x$;
$p\#$ - праймориал, то есть произведение простых чисел от 1 до $p$ ($2*3*5*7*...*p$)

Важное замечание!!!
$[x]$ - это именно целая часть числа $x$, а не округление числа $x$.
То есть $[\dfrac{1}{2}]=0;$ $[\dfrac{5}{6}]=0;$ $[\dfrac{5}{2}]=2$ и так далее.

Цитата:

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

Для определения количества простых чисел от 1 до N, мне нужно будет знать не все простые числа от 1 до N, а лишь некоторую часть. Более точную оценку попробую сделать позже (вечером)

[Батороев]

Rasulka в сообщении #235893 писал(а):

Для определения количества простых чисел от 1 до N, мне нужно будет знать не все простые числа от 1 до N, а лишь некоторую часть. Более точную оценку попробую сделать позже (вечером)

Не майтесь: $p$ - наибольшее простое, не превышающее $\sqrt N$ (если речь идет о точной формуле расчета количества простых).
Заодно спрошу, какой ответ получается по Вашей формуле для $N=100$?

[Xaositect]

Я тут проверил, формула начинает превышать правильное количество простых чисел при $N=25$, и это расхождение постепенно увеличивается, при $N=100$ расхождение составляет $6$, при $N=1000$ - $129$.
Cкачки происходят при $N=25(5^2),49(7^2),55(5\cdot 11),77(7\cdot 11),85(5\cdot 17),91(7\cdot 13)$. Видимо, Вы в доказательстве где-то не учитываете степени простых чисел и произведения простых чисел, идущих не подряд.

[maxal]

Вы пытаетесь переоткрыть формулу Лежандра:
http://mathworld.wolfram.com/LegendresFormula.html