How to prove this prime counting method is correct?

169 Views Asked by At

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