∑MathAdvanced

Möbius Function and Inversion

Key Points

•
The Möbius function $μ (n)$ is 0 if n has a squared prime factor, otherwise it is (-1)^k where k is the number of distinct prime factors.
•
Dirichlet convolution turns divisor sums into products, and the Möbius function is the multiplicative inverse of the constant-one function under this convolution.
•
Möbius inversion says that if g(n) = $\sum_{d ∣ n}$ f(d), then f(n) = $\sum_{d ∣ n}$ $μ$ (d) g $\frac{n}{d}$ .
•
You can count coprime pairs by summing $μ$ (d) $⌊$ n/d $⌋$ $⌊$ m/d $⌋$ over d, and speed it up with harmonic grouping.
•
The number of squarefree integers up to N equals $\sum_{k = 1}^{⌊ N ⌋}$ $μ$ (k) $⌊$ N/ $k^{2}$ $⌋$ .
•
A linear sieve computes $μ (1.. N)$ in O(N) time and is essential for large constraints.
•
Möbius inversion is an inclusion–exclusion principle over divisors, so sign patterns mirror counting-with-avoidance problems.
•
Careful integer arithmetic and 64-bit types are required to avoid overflow in sums involving floor divisions.

Prerequisites

→Prime factorization and sieve of Eratosthenes — Understanding primes and efficient sieving is essential to compute μ and to reason about squarefree numbers.
→Greatest common divisor (gcd) and properties — Coprime counting and gcd-based decompositions rely on gcd arithmetic.
→Inclusion–exclusion principle — Möbius inversion mirrors inclusion–exclusion over divisors; the sign pattern comes from it.
→Asymptotic analysis and harmonic sums — To optimize divisor sums using floor functions and grouping, you need comfort with O(√n) decompositions.
→Multiplicative functions and Dirichlet convolution — Inversion is framed in terms of Dirichlet convolution; knowing this algebra simplifies derivations.
→Integer arithmetic and 64-bit overflow handling — Products of floor terms can exceed 32-bit; robust implementations need 64-bit accumulators.

Detailed Explanation

Tap terms for definitions

01Overview

The Möbius function μ(n) is a small but powerful arithmetic function with values in {−1, 0, +1} that encodes squarefreeness and the parity of distinct prime factors of n. It plays a central role in multiplicative number theory and in transforming divisor-sum relationships via Möbius inversion. In practical problem solving, μ(n) lets you undo sums over divisors: if you only know g(n) as a total over all divisors of n, then μ provides the exact recipe to recover the original f(n). This is the arithmetic counterpart of inclusion–exclusion and is widely used for counting objects under a gcd constraint, deconvolving multiplicative functions, and deriving formulas such as Euler’s totient in terms of μ.

Algorithmically, you can precompute μ(1..N) quickly using a linear sieve. Once μ is available, common tasks include counting coprime pairs (i, j) with 1 ≤ i ≤ n and 1 ≤ j ≤ m, counting squarefree integers up to N, and inverting divisor sums g(n) = ∑_{d|n} f(d) to recover f. These tasks often require optimizing divisor or multiple loops with harmonic grouping to fit within time limits. For competitive programming at the 1900–2300 range, mastering these patterns and their optimizations is crucial.

02Intuition & Analogies

Think of counting with restrictions using inclusion–exclusion. Suppose you want to count numbers up to N that are not divisible by any square. First, count all numbers, then subtract those divisible by p^2 for any prime p, add back those divisible by two different squares, and so on. The signs alternate exactly like (−1)^k, and terms vanish when a square factor is present—this is precisely what the Möbius function encodes.

Another analogy: Imagine you can observe only a blurred version g(n) of a signal f(n), where blur means “sum over all divisors.” Each value g(n) mixes contributions from every f(d) where d divides n. The Möbius function acts like the perfect un-blurring filter. Applying μ to g via a divisor sum cancels precisely the excess contributions and recovers the original f. This is the discrete analog of deconvolution—except the convolution is over divisors (Dirichlet convolution), not over indices.

For coprime counting, picture grouping the grid of points (i, j) by their gcd: every pair has gcd equal to some d, and scaling by d turns it into a coprime pair. Inclusion–exclusion over d with weights μ(d) counts those with gcd 1 by adding and subtracting blocks of size floor(n/d) × floor(m/d). When μ(d) = 0 (i.e., d has a squared prime), that block drops out automatically. The harmonic trick then says many consecutive d share the same floor(n/d) and floor(m/d), so you can sum whole ranges at once.

03Formal Definition

The Möbius function \(

μ

N \to

\{-1,0,1\}\) is defined by \[

μ

(1)=1,

μ

(n)=

\begin{cases}

(-1)^k &

if

n = p_{1}

p_{2} \dots

p_{k}

is a product of

distinct primes

,\\ 0 &

if

is divisible by

p^{2}

for some prime

\end{cases}

\] It is a multiplicative function: if \(

g cd

(m,n)=1\), then \(

μ

(mn)=

μ

(m)

μ

(n)\). For arithmetic functions \(f,g:

N \to C

\), the Dirichlet convolution is \[(f

*

g)(n)=

\sum_{d ∣ n}

f(d)\,g

\frac{n}{d}

.\] Let \(

1

(n)

\equiv

1\). Then \(

μ

\) is the Dirichlet inverse of \(

1

\): \(

μ * 1

ε

\), where \(

ε

(1)=1\) and \(

ε

(n)=0\) for \(

n>1\

). Equivalently, \(

\sum_{d ∣ n} μ

(d)=

ε

(n)\). Möbius inversion: If \(

g=f\ast\mathbf{1}\

), i.e., \(g(n)=

\sum_{d ∣ n}

f(d)\), then \[f=g

* μ

so

f(n)=

\sum_{d ∣ n} μ

(d)\,g

\frac{n}{d}

.\] This identity uniquely recovers $f$ from $g$ whenever the divisor sums are finite (which they are over \(

N

\)).

04When to Use

Use Möbius inversion whenever you have a function presented as a divisor sum and you need to recover the original terms. Classic signs include formulas like g(n) = ∑_{d|n} f(d), or any statement that values at n aggregate contributions from all divisors of n. Typical competitive programming scenarios are:

Counting gcd-constrained pairs: the number of coprime pairs (i, j) with 1 ≤ i ≤ n, 1 ≤ j ≤ m equals ∑_{d=1}^{min(n,m)} μ(d) ⌊n/d⌋ ⌊m/d⌋.
Squarefree counting: the count of integers ≤ N that are squarefree is ∑_{k=1}^{⌊√N⌋} μ(k) ⌊N/k^2⌋.
Inverting multiplicative transforms: given g(n) = ∑{d|n} f(d), compute f via a convolution with μ. This arises in problems with divisor DP, multiplicative function reconstruction, or recovering φ(n) using φ(n) = ∑{d|n} μ(d) n/d.
Removing overcounts on divisors: inclusion–exclusion on factors, such as removing numbers divisible by any of a set of squared primes, or restricting to gcd equal to 1.

Apply harmonic decomposition when summing expressions with floor(n/d) to reduce time from O(n) to roughly O(√n). Precompute μ up to N with a linear sieve when you have many queries or large bounds.

⚠️Common Mistakes

Forgetting μ(1) = 1 or misclassifying primes squared: ensure μ(n) = 0 whenever n has any squared prime factor. A common bug is setting μ(p^2) = −1 instead of 0.
Confusing standard convolution with Dirichlet convolution: divisor sums use Dirichlet convolution, not the index-based convolution seen in FFT problems. The loops iterate over divisors/multiples, not over offsets.
Overflow with floors: expressions like ⌊n/d⌋⌊m/d⌋ can exceed 32-bit; always use 64-bit integers (long long) for products and totals.
Inefficient O(n^2) divisor loops: computing f from g via naive nested divisor checks is too slow for N up to 10^6. Use the standard multiples loop f[d·k] += μ[d]·g[k] to achieve O(N log N), or even faster via prime factorization in special cases.
Not using harmonic grouping: directly summing ∑ μ(d)⌊n/d⌋⌊m/d⌋ in O(n) will TLE for n ≈ 10^7. Group by equal quotient intervals using prefix sums of μ to get O(√n) behavior.
Precomputing μ to the wrong bound: for squarefree counts up to N you only need μ up to √N, but for pair counts up to (n, m) you need up to min(n, m). Choosing too small a limit yields wrong answers; too large wastes time and memory.
Assuming μ is nonnegative or monotone: μ oscillates; do not expect cancellations unless justified. Always compute exact sums.

Key Formulas

Möbius Function

μ (n) = ⎩ ⎨ ⎧ 1 (- 1)^{k} 0 n = 1, n = p_{1} p_{2} \dots p_{k} with distinct primes, p^{2} ∣ n for some prime p .

Explanation: This defines μ by squarefreeness and the parity of the number of distinct prime factors. It is zero exactly when n has a squared prime factor.

Dirichlet Convolution

(f * g) (n) = d ∣ n \sum f (d) g (n / d)

Explanation: This operation combines two arithmetic functions by summing over divisors. It is the natural product when working with divisor sums.

Key Identity

d ∣ n \sum μ (d) = ε (n) = {10 n = 1, n > 1.

Explanation: μ is the inverse of the constant-one function under Dirichlet convolution. Summing μ over all divisors cancels to zero unless $n = 1$ .

Möbius Inversion

g (n) = d ∣ n \sum f (d) ⟺ f (n) = d ∣ n \sum μ (d) g (n / d)

Explanation: If g is the divisor-sum transform of f, then the original f is obtained by convolving g with $μ .$ This is the inversion principle.

Coprime Pair Count

d = 1 \sum m i n (n, m) μ (d) ⌊ \frac{n}{d} ⌋ ⌊ \frac{m}{d} ⌋

Explanation: Counts pairs (i, j) with gcd(i, j) = 1 by inclusion–exclusion over the common gcd d. Each term counts pairs where both are multiples of d.

Squarefree Counting

Q (N) = k = 1 \sum ⌊ N ⌋ μ (k) ⌊ \frac{N}{k ^{2}} ⌋

Explanation: Counts integers up to N that are not divisible by any prime square. The term for k excludes numbers divisible by $k^{2}$ , with signs from $μ (k) .$

Totient via Möbius

φ (n) = d ∣ n \sum μ (d) \frac{n}{d} = (μ * id) (n)

Explanation: Euler’s totient equals the convolution of μ with the identity function id(n)=n. This is a direct application of inversion.

Dirichlet Series of μ

n = 1 \sum \infty \frac{μ ( n )}{n ^{s}} = \frac{1}{ζ ( s )}, ℜ (s) > 1

Explanation: The generating function of μ is the reciprocal of the Riemann zeta function, reflecting that μ is the inverse of 1 under Dirichlet convolution.

Complexity Analysis

The core primitive is computing

μ (1.. N) .

A linear sieve maintains a list of primes and visits each composite exactly once, giving O(N) time and O(N) space. For N up to 10^7 this is typically feasible in optimized C++ (memory ~ a few arrays of N integers/bytes). If N is larger or memory is tight, a segmented approach or using only up to √N for squarefree counting can help. Möbius inversion over an array g[1..N] where g(n) =

\sum_{d ∣ n}

f(d) can be computed for all n in O(N log N) time using the multiples method: for each d, add

μ (d) \cdot g (k)

to f(d·k) for k up to N/d. The number of updates is ∑_{

d\leqN}

⌊N/d⌋ = O(N log N). Space is O(N) for arrays f, g, and

μ .

Coprime pair counting uses the sum ∑

μ (d) ⌊ n / d ⌋ ⌊ m / d ⌋ .

A naive O(min(n, m)) loop is too slow for large inputs. With harmonic grouping and the Mertens prefix M(x) = ∑_{

d\leqx}

μ (d),

the number of iterations becomes O(√(min(n, m))) since ⌊n/d⌋ and ⌊m/d⌋ change only O(√n) times. Precomputing μ and M up to min(n, m) is O(N), and each query then runs in roughly O(√N) time using 64-bit arithmetic. Space is O(N). Squarefree counting up to N requires μ up to √N, with time O(√N) for both the sieve and the summation. This is highly efficient and suitable for very large N (e.g., up to 10^12 or more) when using 64-bit types. In all cases, prefer int64 for accumulators to avoid overflow in products like ⌊n/d⌋⌊m/d⌋.

Code Examples

Linear sieve to compute Möbius function μ(1..N) and Mertens prefix M(n)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes mu[1..N] with a linear (Euler) sieve.
5 // Also computes M[n] = sum_{k=1}^n mu[k] (Mertens function prefix).
6 // Time: O(N), Space: O(N)
7 struct MobiusSieve {
8     int N;
9     vector<int> mu, primes;
10     vector<bool> is_composite;
11     vector<int> M; // prefix sums of mu
12 
13     MobiusSieve(int N): N(N), mu(N+1, 0), is_composite(N+1, false), M(N+1, 0) {
14         mu[1] = 1;
15         for (int i = 2; i <= N; ++i) {
16             if (!is_composite[i]) {
17                 primes.push_back(i);
18                 mu[i] = -1; // prime has one distinct prime factor
19             }
20             for (int p : primes) {
21                 long long v = 1LL * i * p;
22                 if (v > N) break;
23                 is_composite[v] = true;
24                 if (i % p == 0) {
25                     mu[v] = 0; // squared prime factor appears
26                     break;     // ensure each composite is processed once for its smallest prime factor
27                 } else {
28                     mu[v] = -mu[i]; // multiply by a new distinct prime
29                 }
30             }
31         }
32         for (int i = 1; i <= N; ++i) M[i] = M[i-1] + mu[i];
33     }
34 };
35 
36 int main() {
37     ios::sync_with_stdio(false);
38     cin.tie(nullptr);
39 
40     int N; 
41     if (!(cin >> N)) return 0;
42     MobiusSieve ms(N);
43 
44     cout << "mu(1.." << N << "):\n";
45     for (int i = 1; i <= min(N, 30); ++i) {
46         cout << "mu(" << i << ") = " << ms.mu[i] << '\n';
47     }
48     cout << "Mertens prefix M(" << N << ") = " << ms.M[N] << '\n';
49     return 0;
50 }
51

This program builds μ using a linear sieve and also computes the Mertens prefix sums M(n) for fast range-sum queries of μ. The sieve marks composites by their smallest prime and sets μ[v] to 0 when a squared prime divides v, or flips sign when multiplying by a new distinct prime.

Time: O(N)Space: O(N)

Möbius inversion to recover f from g where g(n) = sum_{d|n} f(d)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Recovers f from g using f = g * mu (Dirichlet convolution)
5 // Input: N and array g[1..N]
6 // Output: f[1..N] such that g(n) = sum_{d|n} f(d)
7 
8 struct MobiusSieve {
9     int N; vector<int> mu, primes; vector<bool> is_comp;
10     MobiusSieve(int N): N(N), mu(N+1), is_comp(N+1,false) {
11         mu[1]=1; 
12         for (int i=2;i<=N;i++) {
13             if (!is_comp[i]) { primes.push_back(i); mu[i]=-1; }
14             for (int p: primes) {
15                 long long v=1LL*i*p; if (v> N) break; is_comp[v]=true;
16                 if (i%p==0){ mu[v]=0; break; } else mu[v]=-mu[i];
17             }
18         }
19     }
20 };
21 
22 int main(){
23     ios::sync_with_stdio(false); cin.tie(nullptr);
24 
25     int N; if(!(cin>>N)) return 0; 
26     vector<long long> g(N+1), f(N+1, 0);
27     for (int i=1;i<=N;i++) cin>>g[i];
28 
29     MobiusSieve ms(N);
30 
31     // f[n] = sum_{d|n} mu[d] * g[n/d]
32     // Compute all f via multiples loops in O(N log N):
33     for (int d=1; d<=N; ++d) {
34         int mu_d = ms.mu[d];
35         if (mu_d==0) continue;
36         for (int k=1; d*k<=N; ++k) {
37             int n = d*k;
38             f[n] += 1LL * mu_d * g[k];
39         }
40     }
41 
42     for (int i=1;i<=N;i++) cout<<f[i]<<(i==N?'\n':' ');
43     return 0;
44 }
45

Given g with g(n) = ∑_{d|n} f(d), we recover f by f(n) = ∑_{d|n} μ(d) g(n/d). The code computes μ via a linear sieve and then applies the inversion using a multiples loop, which runs in O(N log N).

Time: O(N log N)Space: O(N)

Counting coprime pairs (i, j) with 1 ≤ i ≤ n, 1 ≤ j ≤ m using harmonic grouping

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct MobiusSieve {
5     int N; vector<int> mu, primes; vector<bool> is_comp; vector<int> M;
6     MobiusSieve(int N): N(N), mu(N+1), is_comp(N+1,false), M(N+1,0) {
7         mu[1]=1; 
8         for (int i=2;i<=N;i++){
9             if(!is_comp[i]){primes.push_back(i); mu[i]=-1;}
10             for(int p:primes){ long long v=1LL*i*p; if(v>N) break; is_comp[v]=true; if(i%p==0){ mu[v]=0; break;} else mu[v]=-mu[i]; }
11         }
12         for (int i=1;i<=N;i++) M[i]=M[i-1]+mu[i];
13     }
14 };
15 
16 // Returns number of pairs (i,j) with 1<=i<=n, 1<=j<=m and gcd(i,j)=1.
17 long long count_coprime_pairs(long long n, long long m) {
18     long long K = min(n, m);
19     MobiusSieve ms((int)K);
20     long long ans = 0;
21     // Harmonic grouping over d where floor(n/d) and floor(m/d) are constant
22     for (long long l = 1; l <= K; ) {
23         long long qn = n / l;
24         long long qm = m / l;
25         long long r = min(n / qn, m / qm); // largest r with same quotients
26         long long sum_mu = ms.M[(int)r] - ms.M[(int)l - 1];
27         ans += sum_mu * qn * qm;
28         l = r + 1;
29     }
30     return ans;
31 }
32 
33 int main(){
34     ios::sync_with_stdio(false); cin.tie(nullptr);
35 
36     long long n,m; if(!(cin>>n>>m)) return 0;
37     cout << count_coprime_pairs(n,m) << "\n";
38     return 0;
39 }
40

The number of coprime pairs equals ∑_{d=1}^{min(n,m)} μ(d) ⌊n/d⌋ ⌊m/d⌋. We precompute μ and its prefix M, then use harmonic grouping to jump over ranges of d where the floor quotients are constant, reducing the loop count to about O(√min(n, m)).

Time: O(min(n, m)^(1/2)) after O(min(n, m)) preprocessingSpace: O(min(n, m))

Counting squarefree numbers up to N using μ

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Count of squarefree integers <= N is sum_{k<=sqrt(N)} mu(k) * floor(N/k^2)
5 struct MobiusSieve {
6     int N; vector<int> mu, primes; vector<bool> is_comp;
7     MobiusSieve(int N): N(N), mu(N+1), is_comp(N+1,false) {
8         mu[1]=1; 
9         for (int i=2;i<=N;i++){
10             if(!is_comp[i]){primes.push_back(i); mu[i]=-1;}
11             for(int p:primes){ long long v=1LL*i*p; if(v>N) break; is_comp[v]=true; if(i%p==0){ mu[v]=0; break;} else mu[v]=-mu[i]; }
12         }
13     }
14 };
15 
16 long long count_squarefree(long long N){
17     long long S = sqrtl((long double)N);
18     MobiusSieve ms((int)S);
19     long long ans = 0;
20     for (long long k=1; k<=S; ++k) {
21         if (ms.mu[(int)k]==0) continue;
22         ans += 1LL * ms.mu[(int)k] * (N / (k*k));
23     }
24     return ans;
25 }
26 
27 int main(){
28     ios::sync_with_stdio(false); cin.tie(nullptr);
29 
30     long long N; if(!(cin>>N)) return 0;
31     cout << count_squarefree(N) << "\n";
32     return 0;
33 }
34

Using inclusion–exclusion over k^2, the number of squarefree integers ≤ N is ∑ μ(k) ⌊N/k^2⌋. We only need μ up to √N, making the approach fast even for very large N.

Time: O(√N)Space: O(√N)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes mu[1..N] with a linear (Euler) sieve.
5	// Also computes M[n] = sum_{k=1}^n mu[k] (Mertens function prefix).
6	// Time: O(N), Space: O(N)
7	struct MobiusSieve {
8	int N;
9	vector<int> mu, primes;
10	vector<bool> is_composite;
11	vector<int> M; // prefix sums of mu
12
13	MobiusSieve(int N): N(N), mu(N+1, 0), is_composite(N+1, false), M(N+1, 0) {
14	mu[1] = 1;
15	for (int i = 2; i <= N; ++i) {
16	if (!is_composite[i]) {
17	primes.push_back(i);
18	mu[i] = -1; // prime has one distinct prime factor
19	}
20	for (int p : primes) {
21	long long v = 1LL * i * p;
22	if (v > N) break;
23	is_composite[v] = true;
24	if (i % p == 0) {
25	mu[v] = 0; // squared prime factor appears
26	break; // ensure each composite is processed once for its smallest prime factor
27	} else {
28	mu[v] = -mu[i]; // multiply by a new distinct prime
29	}
30	}
31	}
32	for (int i = 1; i <= N; ++i) M[i] = M[i-1] + mu[i];
33	}
34	};
35
36	int main() {
37	ios::sync_with_stdio(false);
38	cin.tie(nullptr);
39
40	int N;
41	if (!(cin >> N)) return 0;
42	MobiusSieve ms(N);
43
44	cout << "mu(1.." << N << "):\n";
45	for (int i = 1; i <= min(N, 30); ++i) {
46	cout << "mu(" << i << ") = " << ms.mu[i] << '\n';
47	}
48	cout << "Mertens prefix M(" << N << ") = " << ms.M[N] << '\n';
49	return 0;
50	}
51

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Recovers f from g using f = g * mu (Dirichlet convolution)
5	// Input: N and array g[1..N]
6	// Output: f[1..N] such that g(n) = sum_{d\|n} f(d)
7
8	struct MobiusSieve {
9	int N; vector<int> mu, primes; vector<bool> is_comp;
10	MobiusSieve(int N): N(N), mu(N+1), is_comp(N+1,false) {
11	mu[1]=1;
12	for (int i=2;i<=N;i++) {
13	if (!is_comp[i]) { primes.push_back(i); mu[i]=-1; }
14	for (int p: primes) {
15	long long v=1LLip; if (v> N) break; is_comp[v]=true;
16	if (i%p==0){ mu[v]=0; break; } else mu[v]=-mu[i];
17	}
18	}
19	}
20	};
21
22	int main(){
23	ios::sync_with_stdio(false); cin.tie(nullptr);
24
25	int N; if(!(cin>>N)) return 0;
26	vector<long long> g(N+1), f(N+1, 0);
27	for (int i=1;i<=N;i++) cin>>g[i];
28
29	MobiusSieve ms(N);
30
31	// f[n] = sum_{d\|n} mu[d] * g[n/d]
32	// Compute all f via multiples loops in O(N log N):
33	for (int d=1; d<=N; ++d) {
34	int mu_d = ms.mu[d];
35	if (mu_d==0) continue;
36	for (int k=1; d*k<=N; ++k) {
37	int n = d*k;
38	f[n] += 1LL * mu_d * g[k];
39	}
40	}
41
42	for (int i=1;i<=N;i++) cout<<f[i]<<(i==N?'\n':' ');
43	return 0;
44	}
45

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Count of squarefree integers <= N is sum_{k<=sqrt(N)} mu(k) * floor(N/k^2)
5	struct MobiusSieve {
6	int N; vector<int> mu, primes; vector<bool> is_comp;
7	MobiusSieve(int N): N(N), mu(N+1), is_comp(N+1,false) {
8	mu[1]=1;
9	for (int i=2;i<=N;i++){
10	if(!is_comp[i]){primes.push_back(i); mu[i]=-1;}
11	for(int p:primes){ long long v=1LLip; if(v>N) break; is_comp[v]=true; if(i%p==0){ mu[v]=0; break;} else mu[v]=-mu[i]; }
12	}
13	}
14	};
15
16	long long count_squarefree(long long N){
17	long long S = sqrtl((long double)N);
18	MobiusSieve ms((int)S);
19	long long ans = 0;
20	for (long long k=1; k<=S; ++k) {
21	if (ms.mu[(int)k]==0) continue;
22	ans += 1LL * ms.mu[(int)k] * (N / (k*k));
23	}
24	return ans;
25	}
26
27	int main(){
28	ios::sync_with_stdio(false); cin.tie(nullptr);
29
30	long long N; if(!(cin>>N)) return 0;
31	cout << count_squarefree(N) << "\n";
32	return 0;
33	}
34