题意：给你一个数列，和m个询问，求 数组种 l -r 中所有质数的的倍数的个数和。
解题思路：变形筛法。注意细节
解题代码：
1 // File Name: 385c.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月07日 星期六 18时24分53秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 using namespace std; 26 const int maxn = 1000000*10 + 1000; 27 int ans[maxn]; 28 int hs[maxn]; 29 int ahs[maxn]; 30 int n ; 31 void solve() 32 { 33 //int tmp = sqrt(maxn); 34 for(int i = 2;i < maxn;i ++) 35 { 36 if(hs[i] == 0) 37 { 38 for(int j = i ;j < maxn;j += i) 39 { 40 41 ans[i] += ahs[j] ; 42 hs[j] = 1; 43 } 44 } 45 } 46 for(int i = 2;i <= maxn;i ++) 47 { 48 ans[i] += ans[i-1]; 49 } 50 } 51 int main(){ 52 memset(ans,0,sizeof(ans)); 53 memset(hs,0,sizeof(hs)); 54 memset(ahs,0,sizeof(ahs)); 55 scanf("%d",&n); 56 int _max = 0; 57 for(int i = 1;i <= n;i ++) 58 { 59 int tmp ; 60 scanf("%d",&tmp); 61 ahs[tmp] ++; 62 _max = max(tmp,_max); 63 } 64 solve(); 65 int m ; 66 scanf("%d",&m); 67 for(int i = 1;i <= m;i ++) 68 { 69 int l , r; 70 scanf("%d %d",&l,&r); 71 if(l > _max) 72 { 73 printf("0 "); 74 continue; 75 } 76 r = min(r,_max); 77 printf("%d ",ans[r] - ans[l-1]); 78 } 79 return 0; 80 }