Module: The Euler function and other problems in number theory


Problem

1 /9


Euler function

Theory Click to read/hide

Euler function

The theory can be read here.

Problem

Given a natural number \(n  <= 10^9,\) determine the number of natural numbers less than \(n\ ) and coprime to \(n\). This number is denoted by \( f(n) \) and is called Euler's phi function. The complexity of the algorithm should be \( O(\sqrt{n})\) .

Input
The input is a natural number n.

Imprint
Print the answer to the problem.
 

 

Examples
# Input Output
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!