2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 01:03 
Аватара пользователя
формулы не встречал, но при не очень больших N , можно применить решето эратосфена! конечно не очень удобно....

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

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 01:05 
Аватара пользователя
Да, но науке она не известна, т.к. она действительно зависит от порядка числа на числовой оси: чем оно больше, тем и формула сложнее.

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 01:06 
Аватара пользователя
Rasulka в сообщении #235461 писал(а):
Много раз уже встречал формулы, по которым можно лишь приближенно оценить количество простых чисел от 1 до N. У меня возник вопрос, существует ли формула для нахождения точного количества простых чисел от 1 до N, пусть даже эта формула будет бесконечной?

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 09:49 
Если через $ \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 писал(а):

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 11:27 
Аватара пользователя
Rasulka в сообщении #235461 писал(а):
...формула для нахождения точного количества простых чисел от 1 до N, пусть даже эта формула будет бесконечной?


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

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 16:38 
Просто я пытался вывести формулу и она у меня получилась. Стал искать подобную формулу в интернете, нашёл различные формулы, но точно такую же, как и у меня не нашёл.
Вот она:$\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 --

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

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 17:15 
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}]...$
Только статья даже не на тему"К-во простых" а про "Формулу включений и исключений"

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 17:21 
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}]...$

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 17:25 
Цитата:
Вы считаете Ваша формула даёт точное количество простых чисел?


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

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

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 17:42 
Rasulka в сообщении #235888 писал(а):
Да, её я проверял и не один раз. А что, есть какие-то сомнения по поводу её правильности?

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

P.S.
Rasulka в сообщении #235877 писал(а):
И ещё вопрос, как поставить знак праймориал "#" в коде math?

$ \sharp,\ \# $

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 18:14 
Формулу необходимо подкорректировать.
Правильнее будет так:
$\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, а лишь некоторую часть. Более точную оценку попробую сделать позже (вечером) :!:

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 18:41 
Rasulka в сообщении #235893 писал(а):
Для определения количества простых чисел от 1 до N, мне нужно будет знать не все простые числа от 1 до N, а лишь некоторую часть. Более точную оценку попробую сделать позже (вечером) :!:

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

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 19:16 
Аватара пользователя
Я тут проверил, формула начинает превышать правильное количество простых чисел при $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)$. Видимо, Вы в доказательстве где-то не учитываете степени простых чисел и произведения простых чисел, идущих не подряд.

 
 
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение18.08.2009, 02:14 
Аватара пользователя
Вы пытаетесь переоткрыть формулу Лежандра:
http://mathworld.wolfram.com/LegendresFormula.html

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group