2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 00:56 


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

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


15/08/09
1458
МГУ
формулы не встречал, но при не очень больших N , можно применить решето эратосфена! конечно не очень удобно....

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

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

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


17/06/09

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

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


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

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

 Профиль  
                  
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение16.08.2009, 09:49 


23/01/07
3415
Новосибирск
Если через $ \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 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Rasulka в сообщении #235461 писал(а):
...формула для нахождения точного количества простых чисел от 1 до N, пусть даже эта формула будет бесконечной?


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

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

 Профиль  
                  
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 16:38 


20/09/08
34
Йошкар-Ола
Просто я пытался вывести формулу и она у меня получилась. Стал искать подобную формулу в интернете, нашёл различные формулы, но точно такую же, как и у меня не нашёл.
Вот она:$\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 


25/05/09
231
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 


21/06/09
60
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 


20/09/08
34
Йошкар-Ола
Цитата:
Вы считаете Ваша формула даёт точное количество простых чисел?


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

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

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

 Профиль  
                  
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 17:42 


21/06/09
60
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 


20/09/08
34
Йошкар-Ола
Формулу необходимо подкорректировать.
Правильнее будет так:
$\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 


23/01/07
3415
Новосибирск
Rasulka в сообщении #235893 писал(а):
Для определения количества простых чисел от 1 до N, мне нужно будет знать не все простые числа от 1 до N, а лишь некоторую часть. Более точную оценку попробую сделать позже (вечером) :!:

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

 Профиль  
                  
 
 Re: Существует ли формула для определения кол-ва простых чисел?
Сообщение17.08.2009, 19:16 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Я тут проверил, формула начинает превышать правильное количество простых чисел при $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 
Модератор
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group