题解 | #质数数量#

输入描述:

第一行输入一个整数T，表示询问的个数
接下来T行每行输入一个整数n.
1<=T<=1e8,1<=n<=1000000

输出描述:

对于每个询问n输出小于等于n的的质数的个数。

# 欧拉筛法 True代表质数，False代表合数
num = 1000000
lis1 = [True for i in range(num + 1)]  # 记录合数
lis2 = []  # 保存质数
for i in range(2, num + 1):
    if lis1[i]:
        lis2.append(i)
    for prime in lis2:
        if i * prime > num:
            break
        lis1[i * prime] = False
        if i % prime == 0:
            break
del lis1[0]  # 因为列表里第一个代表的是0 所以我们把0删掉，现在列表的每个元素分别代表1~1000000
lis1[0] = 0  # 此时将列表里第一个元素改为0，因为此时1 对应的质数个数为零
# 然后依次对每个元素对应的质数个数进行统计
c = 0
for i in range(1, len(lis1)):  # 下标从1（第二个元素）开始，因为第一个元素我们在上面已经更改过了
    if lis1[i] == True:
        c += 1
        lis1[i] = c
    if lis1[i] == False:
        lis1[i] = c

n = int(input())
lis = []  # 把要查找的数放在列表中，方便以后查询
for i in range(n):
    lis.append(int(input()))
# 最后循环查找对应的个数
for i in lis:
    print(lis1[i-1])  # 因为下标是从0计算的，但我们这里认为第一个元素是1，所以下标要减一