Euler Problem 193
=================

A positive integer n is called squarefree, if no square of a prime divides n,
thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.

How many squarefree numbers are there below 2<sup>50</sup>?


```python
from sympy import sieve
N = 2**25
NN = N*N - 1
mobius = [0, 1, -1, 1] * ((N+3) // 4)
mobius[0] = 1
for p in sieve.primerange(3, N):
    for n in range(p, N, p):
        mobius[n] = -mobius[n]
    pp = p*p
    for n in range(pp, N, pp):
        mobius[n] = 0
print(sum(int(NN/(d*d)) * mobius[d] 
          for d in range(1, N)))
```

    684465067343069



```python

```

4687be0db0ba725eaddc8d8b56b358a1edc907b7
ipynb
Jupyter Notebook
Euler 193 - Squarefree numbers.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
2016-05-11T18:55:35.000Z
2019-12-27T21:38:43.000Z
Euler 193 - Squarefree numbers.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
Euler 193 - Squarefree numbers.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
Qwen/Qwen-72B
1. YES
2. YES