## Algorithm

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 0 12 , 1 12 , 2 12 , 3 12 , 4 12 , 5 12 , 6 12 , 7 12 , 8 12 , 9 12 , 10 12 , 11 12 Reduction yields 0 12 , 1 12 , 1 6 , 1 4 , 1 3 , 5 12 , 1 2 , 7 12 , 2 3 , 3 4 , 5 6 , 11 12 Hence there are only the following 4 irreducible basic fractions with denominator 12 0 12 , 5 12 , 7 12 , 11 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 12 123456 7654321 0

Sample Output 4 41088 7251444

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

`````` #include <bits/stdc++.h>
using namespace std;
#define N 40000 // larger than sqrt of 1e9

vector<int> primes;

void sieve(){
primes.clear();
bitset < N> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = false;
for(long long i=2;i i+It N;i++){
if(isPrime[i]) {
primes.push_back(i);
for(long long j=i*i;j i+It N;j+=i)
isPrime[j] = false;
}
}
}

// Eulter's Phi (Totient) function
// number of positive integers coprime to n, gcd(x,n) = 1
// basic idea of euler's phi is to remove fraction that is a factor of the prime
// N * mul(1-1/PF) for all PF
int eulerPhi(int n) {
int ans = n; // itself
for(int idx=0;primes[idx]*primes[idx] <= n; idx++) {
if (n % primes[idx] == 0) ans -= ans/primes[idx];
while(n % primes[idx] == 0) {
n /= primes[idx];
}
}
if (n != 1) ans -= ans/n;
return ans;
}

int main()
{
sieve();
int n;
while(scanf("%d",&n),n) {
printf("%d\n", eulerPhi(n)>;
}
}``````
Copy The Code &

Input

cmd
12
123456
7654321
0

Output

cmd
4
41088
7251444