题解 | #质数数量#

埃氏筛

首先标记所有数字都是质数，然后如果x是质数，分别标记2*x 3*x,... 为非质数，然后使用前缀和，求得前i个数中质数的数量，保证后面的n个询问都能以O(1)的时间回答出来

N=1000010
primes=[1]*(N+1)
primes[0]=primes[1]=0
i=2
while i*i<=N:
    j=2
    while i*j<=N: 
        primes[i*j]=0
        j+=1
    i+=1
for i in range(N):
    primes[i]+=primes[i-1]

    

n=int(input())
for i in range(n):
    print(primes[int(input())])