Coprimes

Problem Description

For given integer N (1<=N<=10^4) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

Input

Input file contains integer N.

Output

Write answer in output file.

Sample Input

1
9

Sample Output

1
6

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);

int n;
std::cin >> n;

int ans = n;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
ans -= ans / i;
while(n % i == 0) {
n /= i;
}
}
}

if(n > 1) {
ans -= ans / n;
}

std::cout << ans << std::endl;

return 0;
}