<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

102. Coprimes

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


For given integer N (1<=N<=104) 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

9
Sample Output

6

<|response|>
1. Abridged Problem Statement  
Given a positive integer N (1 ≤ N ≤ 10 000), compute how many integers i in the range [1..N] satisfy gcd(i, N) = 1.

2. Key Observations  
- The quantity we want is exactly Euler’s totient function φ(N).  
- Definition: φ(N) is the count of integers from 1 to N that are coprime with N.  
- Two common ways to compute φ(N):  
  a. Brute‐force gcd: for each i from 1 to N compute gcd(i, N) and count how many times it equals 1. Runs in O(N·log N), fast enough for N ≤ 10⁴.  
  b. Using the formula  
     φ(N) = N · ∏_{p | N} (1 – 1/p),  
    where the product runs over the distinct prime divisors p of N. Factorizing N by trial division up to √N takes O(√N), then applying the formula is O(number of prime factors).  

3. Full Solution Approach  
Step 1. Read N.  
Step 2. Handle the trivial case N = 1: φ(1) = 1.  
Step 3. Factorize N by trial division:  
    • Initialize result = N.  
    • For each prime candidate p from 2 up to √N:  
        – If p divides N, then p is a prime factor.  
        – While p divides N, divide N by p.  
        – Update result = result – result/p.  
    • After the loop, if the remaining N > 1 then it is itself a prime > √(original N). In that case do result = result – result/N.  
Step 4. The variable result now holds φ(original N).  
Step 5. Print result.

This runs in O(√N), which is more than fast enough for N ≤ 10⁴ and teaches the classic totient‐function technique.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Compute Euler's totient function φ(n) by prime factorization.
int compute_phi(int n) {
    int result = n;    // Start with φ(n) = n
    int x = n;

    // Check divisibility by 2 first to handle even factors
    if (x % 2 == 0) {
        // 2 is a prime divisor: apply φ = φ * (1 - 1/2)
        result -= result / 2;
        // Remove all factors of 2
        while (x % 2 == 0) {
            x /= 2;
        }
    }

    // Now check odd potential factors from 3 up to sqrt(x)
    for (int p = 3; p * p <= x; p += 2) {
        if (x % p == 0) {
            // p is a prime divisor: apply φ = φ * (1 - 1/p)
            result -= result / p;
            // Remove all occurrences of p
            while (x % p == 0) {
                x /= p;
            }
        }
    }

    // If x > 1, then x itself is a prime factor greater than sqrt(original n)
    if (x > 1) {
        result -= result / x;
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Edge case: φ(1) = 1
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }

    // Compute and output the totient
    cout << compute_phi(n) << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
import math

def compute_phi(n):
    """
    Compute Euler's totient φ(n) by trial‐division factorization.
    """
    result = n
    x = n

    # Handle factor 2 separately
    if x % 2 == 0:
        result -= result // 2
        while x % 2 == 0:
            x //= 2

    # Check odd factors up to sqrt(x)
    p = 3
    while p * p <= x:
        if x % p == 0:
            result -= result // p
            while x % p == 0:
                x //= p
        p += 2

    # If anything remains >1, it is prime
    if x > 1:
        result -= result // x

    return result

def main():
    data = sys.stdin.readline().strip()
    if not data:
        return
    n = int(data)

    # φ(1) = 1 by definition
    if n == 1:
        print(1)
    else:
        print(compute_phi(n))

if __name__ == "__main__":
    main()
```

Explanation of the main steps:  
- We factor N by removing each prime divisor once, updating the totient via `result -= result / p`.  
- After all small factors are removed, any leftover `x > 1` must be a prime > √N, so we apply the same formula one last time.  
- The final `result` is φ(N), the count of integers in [1..N] coprime with N.