Module: La funzione di Eulero e altri problemi di teoria dei numeri


Problem

1 /9


Funzione di Eulero

Theory Click to read/hide

Funzione di Eulero

La teoria può essere letta qui.

Problem

Dato un numero naturale \(n  <= 10^9,\) determina il numero di numeri naturali minori di \ (n\ ) e coprimo in \(n\). Questo numero è indicato da \( f(n) \) ed è chiamato funzione phi di Eulero. La complessità dell'algoritmo dovrebbe essere \( O(\sqrt{n})\) .

Inserimento
L'input è un numero naturale n.

Impressum
Stampa la risposta al problema.
 

 

Esempi
# Input Uscita
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!