UVa 10299

From Algorithmist
Jump to navigation Jump to search

10299 - Relatives[edit]

Summary[edit]

Find number of integers less than n which is relatively prime to n.

Explanation[edit]

What they are asking for is actually to find the value of the Euler's Phi function for n. So just apply the formula to find the Euler's Phi function and you would get the answer.

There is one catch though. Phi(1)=1 but here you need to find all numbers LESS than n and hence for n=1, the ans. is 0.

Input[edit]

7
12
0

Output[edit]

6
4