质数数量 题解 链接:质数数量 题目描述: 质数(prime number)又称素数,有无限个,质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。 例如小于10的质数有2,3,5,7。 输入描述: 第一行输入一个整数T,表示询问的个数。 接下来T行每行输入一个整数n. 1<=T<=1e8,1<=n<=1000000 输出描述: 对于每个询问n输出小于等于n的的质数的个数。 思路: T比较大,暴力会超时,采取打表后查找方式。 打表思路: 只判断奇数,所以 i+=2 判断到 prime[j]∗prime[j]<=iprime[j]*prim...