B385C掛，Codeforces 385 C Bear and Prime Numbers

題目鏈接~~>

做題感悟：這題屬于想法題，比賽時直接做的 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 ;
}