Module: A função de Euler e outros problemas na teoria dos números


Problem

1 /9


Função de Euler

Theory Click to read/hide

Função de Euler

A teoria pode ser lida aqui.

Problem

Dado um número natural \(n  <= 10^9,\) determine o número de números naturais menores que \ (n\ ) e coprime para \(n\). Esse número é denotado por \( f(n) \) e é chamado de função phi de Euler. A complexidade do algoritmo deve ser \( O(\sqrt{n})\) .

Entrada
A entrada é um número natural n.

Impressão
Imprima a resposta para o problema.
 

 

Exemplos
# Entrada Saída
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!