题目链接：http://codeforces.com/problemset/problem/385/C
题目大意：给定n个数与m个询问区间，问每个询问区间中的所有素数在这n个数中被能整除的次数之和
解题思路：首先暴力打出一张素数表，最大的素数小于等于n个数中的最大值即可。在打表的过程就统计从2开始到当前素数的总的整除次数(简直简单粗暴),最后对于询问区间，找出该区间内的最小素数与最大素数在素数表中的位置,结果即为s[r]-s[l-1]
代码如下：
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define maxn 10000005 8 int now,t; 9 int c[maxn],f[maxn],s[maxn]; 10 bool prime[maxn]; 11 12 void solve(int x) 13 { 14 t=0; 15 int i,j; 16 for(i=2;i<=x;i++) 17 { 18 if(!prime[i]) 19 { 20 prime[i]=true; 21 f[now]=i; 22 t+=c[i]; 23 // s[i]+=c[i]; 24 for(j=i+i;j<=x;j+=i) 25 { 26 prime[j]=true; 27 t+=c[j]; 28 } 29 s[now]=t; 30 now++; 31 } 32 } 33 } 34 35 int lfind(int x)//找大于等于x的最小值 36 { 37 int l=0,r=now-1,mid; 38 while(l<=r) 39 { 40 mid=(l+r)/2; 41 if(f[mid]>=x) 42 { 43 r=mid-1; 44 } 45 else 46 l=mid+1; 47 } 48 return l; 49 } 50 51 int rfind(int x)//找小于等于x的最大值 52 { 53 int l=0,r=now-1,mid; 54 while(l<=r) 55 { 56 mid=(l+r)/2; 57 if(f[mid]<=x) 58 l=mid+1; 59 else 60 r=mid-1; 61 } 62 return r; 63 64 } 65 int main() 66 { 67 int n,x; 68 scanf("%d",&n); 69 int Max=0; 70 now=0; 71 memset(prime,false,sizeof(prime)); 72 memset(c,0,sizeof(c)); 73 memset(f,0,sizeof(f)); 74 memset(s,0,sizeof(s)); 75 for(int i=0;i<n;i++) 76 { 77 scanf("%d",&x); 78 if(x>Max) 79 Max=x; 80 c[x]++; 81 } 82 solve(Max); 83 int m,l,r; 84 scanf("%d",&m); 85 while(m--) 86 { 87 scanf("%d%d",&l,&r); 88 int t1=lfind(l); 89 int t2=rfind(r); 90 // cout<<t1<<' '<<t2<<endl; 91 // cout<<f[t1]<<' '<<f[t2]<<endl; 92 if(t1==0) 93 { 94 printf("%d ",s[t2]); 95 } 96 else 97 printf("%d ",s[t2]-s[t1-1]); 98 } 99 100 return 0; 101 }