Количество простых чисел.

[Батороев]

Если через $ \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} $.

[Сомик]

а в чем вопрос то ?

[Батороев]

Сомик писал(а):

а в чем вопрос то ?

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

[maxal]

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