1391. How Many Are Squarefree
Count the integers from 1 to n that are squarefree, meaning no perfect
square above 1 divides them.
n = 10 -> 7 1 2 3 5 6 7 10 are squarefree; 4 8 9 are not
n = 1 -> 1 1 is squarefree, since it has no square factor at all
n = 4 -> 3
## What most people try first
Factorise each value and reject it if any exponent is 2 or more. That is
O(n sqrt(n)), hopeless at n = 10^10. Sieving the multiples of each square
and counting survivors is O(n log log n) but needs an array of n entries,
which is 10 gigabytes.
## Count the bad ones by inclusion and exclusion
A value fails exactly when it is divisible by p^2 for some prime p. So
subtract the multiples of 4, the multiples of 9, the multiples of 25, and
so on, then add back the ones removed twice (multiples of 36, of 100), and
so on. That alternating pattern is exactly the Mobius function:
answer = sum over d from 1 to sqrt(n) of mu(d) * floor(n / d^2)
where mu(d) is 0 if d has a repeated prime factor, +1 if d is a
product of an even number of distinct primes, and -1 if an odd number.
n = 10, sqrt = 3
d=1 mu=+1 floor(10/1) = 10
d=2 mu=-1 floor(10/4) = 2 -> -2
d=3 mu=-1 floor(10/9) = 1 -> -1
total 7
Only d up to sqrt(n) matters, because d^2 > n contributes floor(n/d^2)
of 0. That is 10^5 terms at n = 10^10, so the whole answer is a short
loop over a Mobius table sieved to 10^5.
## Why the formula is right
Every integer m is uniquely d^2 * s with s squarefree, where d^2 is the
largest square dividing m. Group the values 1..n by that d. The count
with a given d is the number of squarefree s at most n/d^2. So
n = sum over d of Q(floor(n / d^2))
where Q is the answer we want. Mobius inversion of that identity gives the
sum above. The identity itself is also a usable algorithm, by recursion, and
the oracle for this problem uses exactly that as an independent check, since it
mentions no Mobius function at all.
## Overflow
n reaches 10^10, which does not fit in a signed 32-bit integer, since
INT_MAX is 2147483647, and d * d reaches 10^10 as well. The answer is
about 0.6079 * n, so about 6 * 10^9, also past 32 bits: a 32-bit build
answers 857217001 where the truth is 6079270942. In JavaScript all of these
stay below 2^53, so a plain Number is exact.
## Cost
O(sqrt(n)) after an O(sqrt(n)) Mobius sieve.
Constraints - `1 ≤ n ≤ 10000000000`
Input
One line with the integer n.
Output
Print the number of squarefree integers from 1 to n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.