Задача

[tanas]

Нека f(n) е броят естествени числа k, по-малки от n, за които е в сила (n,k)=1, т.е. които са взаимнопрости с n.

Да се намери f(100).

[Реклама]

[_sssss]

Всички прости преди 100 --> 23
[tex]\normal 3^2, \; 3^3, \; 3^4 \\ 7^2[/tex]
[tex]\normal 3 \cdot x[/tex] (x-просто, 7<=x<= 31) --> 8
[tex]\normal 7 \cdot x[/tex] (x-просто, 11<=x<= 13) --> 2
[tex]\normal 9 \cdot x[/tex] (x-просто, 7<=x<= 11) --> 3

f(100)=40

[Пафнутий]

Интересно защо никой не е писал по тази тема толкова време... Това е функцията на Ойлер и си има точна формула: ако [tex]n=p_{1}^{s_{1}}....p_{n}^{s_{n}}[/tex] е каноничното разлагане на прости множитeли на [tex]n[/tex] ,то [tex]\varphi(n)=n(1-\frac{1}{p_{1}})...(1-\frac{1}{p_{n}})[/tex]. За повече справка Euler totien function.
ПП По решението на звездите - безсмислено е да броиш простите до 100. Интересува те броя на всички нечетни и некратни на 5 числа до 100...