University of Alberta

Courses/ CMPUT-403/ CMPUT-403-W20/ Week 09: Number Theory/ Problems/ Relatives
Log in
Hide

Problem C
Relatives

/problems/relatives/file/statement/en/img-0001.jpg
Given $n$, a positive integer, how many positive integers less than $n$ are relatively prime to $n$? Two integers $a$ and $b$ are relatively prime if there are no integers $x \ge 2, y \ge 1, z \ge 1$ such that $a = xy$ and $b = xz$.

Input

There up to $10$ test cases. For each test case, standard input contains a line with $1\leq n \leq 1\, 000\, 000\, 000$. A line containing $0$ follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input 1 Sample Output 1 
7
12
0

6
4
Hide

Please log in to submit a solution to this problem

Log in