2014 dxdy logo

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

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




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

$ \pi(N) =  \frac{N}{2} + (i - 1) - \varphi(p_1, \frac{N}{p_2}) - \varphi(p_1*p_2, \frac{N}{p_3}) - ... - \varphi(p_1*p_2*...*p_{i-1}, \frac{N}{p_i}) $, (1)
где $ p_1, p_2, p_3,... p_i $ - простые числа 2, 3, 5, 7..., непревышающие $ \sqrt {N} $.

 
 
 
 
Сообщение21.12.2007, 02:06 
Аватара пользователя
а в чем вопрос то ? :)

 
 
 
 
Сообщение21.12.2007, 14:16 
Сомик писал(а):
а в чем вопрос то ? :)

Была одна мысль о том, что количество простых можно подсчитать через функцию Эйлера от примориала простых, непревосходящих $ N $, в котором взаимнопростые примориалу числа расположены очень строго...
но отвлекся на другое. :?
Успел только выяснить (и то гипотетически), что если примориал поделить на $ 2^{i-1}$ частей, где $ i $ - количество простых в примориале, то в каждой из частей, вроде бы, будет одинаковое число взаимнопростых чисел :?:

 
 
 
 Re: Количество простых чисел.
Сообщение22.12.2007, 06:12 
Аватара пользователя
Это формула Лежандра.

 
 
 [ Сообщений: 4 ] 


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