Problem: given $n$ and the set $P$ is primes less than or equal to $\sqrt{n}$, count primes less than or equal to $n$.
Solution: let $B =\{b_i= \lfloor n/\displaystyle\prod_{t \in a_i} t\rfloor,\ a_i\in 2^P,\ b_i = -b_i \ if\ |a_i| \in 2\mathbb Z +1\},\\ $ $\displaystyle\quad\sum_{b\in B} b + |P| - 1$ is number of primes less than or equal to $n$.
How to prove this prime counting method is correct?
Here's the Python vesion:
from primesieve import *
import math
from itertools import chain, combinations
import operator
import functools
def Pi(n):
p = primes(math.ceil(math.sqrt(n) + 0.00001) - 1)
a = []
for i in chain.from_iterable(combinations(p, r) for r in range(1, len(p)+1)):
t = math.floor(n/functools.reduce(operator.mul, i, 1))
if len(i) & 1 == 1:
t *= -1
a.append(t)
return n + sum(a) + len(p) - 1
print(Pi(1000))
# out put: 168