Codeforces385CBearandPrimeNumbers

版权声明：本文为CSDN博主「Bjut_Search2016」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/nyist_zxp/article/details/40020349

题目链接~~>

做题感悟：这题属于想法题，比赛时直接做的 D 题，但是处理坐标处理的头晕眼花的，结果到最后也没AC。

解题思路：

因为查询的时候只考虑素数，so~我们只考虑素数就可以，这就需要筛素数，我们可以在筛素数的同时把某个素数出现的倍数加上，输入的时候只要记录某个数的个数就可以了。

代码：

#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<iomanip>
#include<algorithm>
using namespace std  ;
#define INT long long int
const int INF = 0x3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = 100 + 5 ;
const int MX = 10000000 + 5 ;
int Max ,n ,m ;
bool isprime[MX] ;
int sum[MX] ,num[MX] ;
void init() // 筛法同时记录个数
{
    memset(isprime ,false ,sizeof(isprime)) ;
    memset(sum ,0 ,sizeof(sum)) ;
    for(int i = 2 ;i <= Max ; ++i)
    {
        sum[i] += sum[i-1] ;
        if(!isprime[i])
        {
            sum[i] += num[i] ;
            for(int j = i + i ;j <= Max ; j += i)
            {
                sum[i] += num[j] ;
                isprime[j] = true ;
            }
        }
    }
}
int main()
{
    int x ;
    while(~scanf("%d" ,&n))
    {
        memset(num ,0 ,sizeof(num)) ;
        Max = 0 ;
        for(int i = 0 ;i < n ; ++i)
        {
            scanf("%d" ,&x) ;
            num[x]++ ;         // 记录个数
            Max = max(Max ,x) ;
        }
        init() ;
        scanf("%d" ,&m) ;
        int le ,rt ;
        for(int i = 0 ;i < m ; ++i)
        {
            scanf("%d%d" ,&le ,&rt) ;
            if(rt > Max)  rt = Max ;
            if(le > Max)  cout<<"0"<<endl ;
            else      cout<<sum[rt]-sum[le-1]<<endl ;
        }
    }
    return 0 ;
}