题目链接：Codeforces 385C Bear and Prime Numbers

这题告诉我仅仅有询问没有更新通常是不用线段树的。或者说还有比线段树更简单的方法。

用一个sum数组记录前n项和，这个sum数组在打素数表时候就能够求出来，注意一点求素数的内层循环要改成i。不能再写成i + i或者i * i了。原因想想就明确了。

这学期最后一场比赛也结束了，结果不非常惬意但也还好。

总的来说这学收获还是蛮多的。

近期可能就不再做ACM了吧，可能要复习CET6了吧，可能要复习期末考试的内容了吧。可能要考研了吧。。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int MAX_N = 1000000 * 10 + 1000;

bool primes[MAX_N];

long long sum[MAX_N];

int arr[MAX_N], cnt[MAX_N];

//primes[i] = 0表示i是素数，为1表示i不是素数

void get_primes()

{

    memset(primes,0,sizeof primes);

    primes[0]=primes[1]=1;

    for(int i=2;i<MAX_N;i++)

    {

        sum[i] = sum[i - 1];

        if(!primes[i])

        {

            for(int j=i;j<MAX_N;j+=i)

            {

                sum[i] += cnt[j];

                primes[j]=1;

            }

        }

    }

}

int main()

{

    int n, _max = 0;

    scanf("%d", &n);

    memset(sum, 0, sizeof(sum));

    memset(cnt, 0, sizeof(cnt));

    for(int i = 1; i <= n; i++)

    {

        scanf("%d", &arr[i]);

        cnt[arr[i]]++;

        _max = max(_max, arr[i]);

    }

    get_primes();

    int q, a, b;

    scanf("%d", &q);

    for(int i = 0; i < q; i++)

    {

        scanf("%d%d", &a, &b);

        if(a > _max && b > _max)

            puts("0");

        else

        {

            if(a > _max)

                a = _max;

            if(b > _max)

                b = _max;

            printf("%I64d\n", sum[b] - sum[a - 1]);

        }

    }

    return 0;

}