链接：https://ac.nowcoder.com/acm/problem/22226
来源：牛客网

题目描述

质数（prime number）又称素数，有无限个，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
例如小于10的质数有2，3，5，7。
链接：https://ac.nowcoder.com/acm/problem/22226
来源：牛客网

输入描述: 

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

输出描述: 

对于每个询问n输出小于等于n的的质数的个数。
输入的数太多，不能每次输入都要筛一遍质数
所以我们直接用欧拉筛选法，筛出1000000内的质数
然后统计1~1000000每个数对应的质数个数
最后只需要查表输出即可 
# 欧拉筛法 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，所以下标要减一