Coprime Numbers and Euler's Totient Function

Euler’s totient φ(n) counts integers from 1 through n that are coprime to n. It measures the size of the invertible residue set modulo n and appears in Euler’s theorem, cyclic counting and number-theory preprocessing. For n=1 the count is one by convention: gcd(1,1)=1. We derive the prime-factor formula and implement both a single-value calculation and a separate totient sieve.

Prerequisites: GCD; Prime Factorization; divisibility.

Build the idea

1. 1. Translate coprimality into excluded primes

   A number shares a nontrivial factor with n exactly when it is divisible by at least one prime dividing n. Thus counting coprime numbers means removing multiples of those distinct primes. The exponent of a prime does not introduce a new exclusion condition; its presence, not how many copies it has, determines which candidate integers are forbidden.

2. 2. Derive the product formula

   From 1..n, a fraction 1/p are multiples of a prime divisor p. Excluding several primes by inclusion–exclusion leaves n times ∏(1−1/p). The count is integral because each p divides n; the algorithm computes result−=result/p when encountering each distinct prime, avoiding floating-point fractions.

   $$\phi \left(n\right)=n\prod _{p\mid n}^{\text{distinct prime p}}(1-\frac{1}{p})$$

3. 3. Remove every copy before moving on

   Set remaining=n and result=n. On finding p, subtract result/p once, then divide all p factors out of remaining. If a prime remainder remains, apply its subtraction once too. Repeating the subtraction for every exponent would remove too much. Starting at n=1 runs no prime updates and returns one naturally.

4. 4. Trace twelve

   The distinct prime divisors are 2 and 3. Start result=12; remove multiples of 2 to get 6, then multiply by 1−1/3 through 6−6/3=4. The coprime integers are 1,5,7,11. Notice 12 is not itself counted for n>1, while the stated interval 1..n is still correct.

5. 5. Preprocess many values

   The totient sieve initializes phi[x]=x. A value p with phi[p]==p is prime; apply phi[x]−=phi[x]/p to every multiple x. After all primes, each x has received one factor for every distinct prime divisor. This reuses work across queries. Euler’s theorem later uses φ(n) only when the base is coprime to n; knowing φ alone does not license arbitrary exponent reduction.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Preprocess many values The totient sieve initializes phi[x]=x.
#include<iostream>
long long totient(long long n){
    long long result=n,remaining=n;
    for(long long p=2;p<=remaining/p;++p){
        if(remaining%p==0){
            result-=result/p;
            do{
                remaining/=p;
            }
            while(remaining%p==0);
        }
    }
    if(remaining>1){
        result-=result/remaining;
    }
    return result;
}
int main(){
    long long n;
    std::cin>>n;
    std::cout<<totient(n)<<'\n';
}

Complexity analysis

Single value: O(√n) trial-division worst-case time and O(1) auxiliary storage. Totient sieve: O(N log log N) time, O(N) memory, O(1) per query. All arithmetic is integral; single input n≤10^12 and sieve bound N≤10^7 are separate contracts.

Example input and output

Read n in 1..10^12 and print φ(n).

Input

12

Output

4

Only 1,5,7,11 are coprime to 12, so φ(12)=4.

Read N q (1≤N≤10^7), then q queries x in 1..N. Print φ(x) for each.

// Key idea: 5. Preprocess many values The totient sieve initializes phi[x]=x.
#include<iostream>
#include<vector>
#include<numeric>
int main(){
    int N,q;
    std::cin>>N>>q;
    std::vector<int>phi(N+1);
    std::iota(phi.begin(),phi.end(),0);
    for(int p=2;p<=N;++p){
        if(phi[p]==p){
            for(int x=p;x<=N;x+=p){
                phi[x]-=phi[x]/p;
            }
        }
    }
    while(q--){
        int x;
        std::cin>>x;
        std::cout<<phi[x]<<'\n';
    }
}

Input

12 3
1
9
12

Output

1
6
4

φ(1)=1; the six integers not divisible by 3 in 1..9 are coprime to 9.

Complexity: O(N log log N) preprocessing and O(N) storage; O(1) each query.

Practical applications

Use for Euler’s theorem, modular inverses via exponentiation under coprimality and counting coprime residue choices. Extended Euclid can find an inverse without factoring a large modulus. A totient sieve is appropriate when many queries share a moderate maximum.

Check your understanding

How often should the update result−=result/p be applied for p³ dividing n?

Put it into practice

Compare φ(n) with counting gcd(k,n)==1 directly for small n.