质数数量 题解

链接：质数数量

题目描述：

质数（prime number）又称素数，有无限个，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

例如小于10的质数有2，3，5，7。

输入描述:

第一行输入一个整数T，表示询问的个数。

接下来T行每行输入一个整数n.

1<=T<=1e8,1<=n<=1000000

输出描述:

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

思路：

T比较大，暴力会超时，采取打表后查找方式。

打表思路：

1. 只判断奇数，所以 i+=2
2. 判断到 即可
3. 判断 i 是否为质数的时候，只需要看 i 是否是表中已经保存的质数的倍数即可

坑：

1. n最大值1e7，打表的时候至少打到1e7+1，否则查询1e7会没输出
2. n=1要特判，直接输出0
3. 最后输出的时候要+1

代码：

#include <bits/stdc++.h>
using namespace std;

int T;
int n;
int prime[100007] = {2, 3, 5, 7};
int len = 4;

int main() {
    for(int i = 11; i <= 1000007; i += 2) {
        bool flag = true;
        for(int j = 0; j < len && prime[j]*prime[j] <= i; j++) {
            if(i % prime[j] == 0) {
                flag = false;
                break;
            }
        }
        if(flag) {
            prime[len++] = i;
        }
    }
    

    cin >> T;
    while(T--) {
        cin >> n;
        if(n == 1) {
            cout << "0" << endl;
            continue;
        }
        for(int j = 0; j < len; j++) {
            if(n >= prime[j] && n < prime[j + 1]) {
                cout << j+1 << endl;
                break;
            }
        }
    }
    return 0;
}