Problem L
Irreducible Basic Fractions
Input: standard input
Output: standard output
Time Limit: 4 seconds
A fraction m / n is basic if 0 <= m < n and it is irreducible if gcd(m, n) = 1. Given a positive integer n, in this problem you are required to find out the number of irreducible basic fractions with denominator n .
For example, the set of all basic fractions with denominator 12, before reduction to lowest terms, is
Reduction yields
Hence there are only the following 4 irreducible basic fractions with denominator 12
Input
Each line of the input contains a positive
integer n (< 1000000000) and the input terminates with a value 0
for n (do not process this terminating value).
Output
For each n in the input print a line containing the number of irreducible basic fractions with denominator n
Sample Input
12Sample Output
Rezaul Alam Chowdhury
“I shot an arrow into the air,
It fell to earth, I knew not where;
For, so swiftly it flew, the sight
Could not follow it in its flight.
I breathed a song into the air,
It fell to earth, I knew not where;
For who has sight so keen and strong,
That it can follow the flight of song?
Long, Long afterward, in an oak
I found the arrow, still unbroke;
And the song from beginning to end,
I found again in the heart of a friend.”