Обработка математики: 100%

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<=109, 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(√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!