质数数量——改进

一开始超时，想到是因为每输入一个n都要从头计算一遍，很多重复工作。
所以改用数组，计算出结果，然后查表即可

#include <iostream>
#include <cmath>

#define N 1000001

bool is_prime(int n);

using namespace std;

int main()
{
    int T, n;
    int a[N];

    a[0] = 0;
    for(int i = 1; i < N; i++)
    {
        a[i] = a[i - 1];
        if(is_prime(i))
        {
            a[i]++;
        }
    }

    cin >> T;
    while(T > 0)
    {
        cin >> n;
        cout << a[n] << endl;
        T--;
    }

    return 0;
}

bool is_prime(int n)
{
    bool res = true;
    if(n < 2)
    {
        return false;
    }
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
        {
            res = false;
            break;
        }
    }
    return res;
}

但看到别人运行速度很快，自己仍然很慢。
看了别人的算法，主要思路是两数相乘的结果肯定不是质数。改进如下

#include <iostream>

#define N 1000001
#define NSQRT 1000

using namespace std;

int main()
{
    int T, n;
    int a[N]={0};                             /*注意初始化，不然结果每次运行都会不同*/

    for(int i = 2; i <= NSQRT; i++)
    {
        if(a[i] == 0)
        {
            for(int j = i*i; j <= N; j += i)
            {
                a[j] = 1;
            }
        }
    }

    for(int i = 2; i < N; i++)
    {
        if(a[i] == 0)
        {
            a[i] = a[i - 1] + 1;
        }
        else
        {
            a[i] = a[i - 1];
        }
    }

    cin >> T;
    while(T > 0)
    {
        cin >> n;
        cout << a[n] << endl;
        T--;
    }

    return 0;
}

节省了每次判断是不是质数时，从2到sqrt(n)的循环