Module: La fonction d'Euler et d'autres problèmes en théorie des nombres


Problem

1 /9


Fonction d'Euler

Theory Click to read/hide

Fonction d'Euler

La théorie peut être lue ici.

Problem

Étant donné un nombre naturel \(n  <= 10^9,\) déterminer le nombre de nombres naturels inférieur à \ (n\ ) et coprime à \(n\). Ce nombre est noté \( f(n) \) et est appelé la fonction phi d'Euler. La complexité de l'algorithme doit être \( O(\sqrt{n})\) .

Entrée
L'entrée est un nombre naturel n.

Mentions légales
Imprimez la réponse au problème.
 

 

Exemples
# Entrée Sortie
1 2 1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!