题目链接：http://codeforces.com/problemset/problem/385/C
题目大意：给定n个数与m个询问区间，问每个询问区间中的所有素数在这n个数中被能整除的次数之和
解题思路：首先暴力打出一张素数表，最大的素数小于等于n个数中的最大值即可。在打表的过程就统计从2开始到当前素数的总的整除次数(简直简单粗暴),最后对于询问区间，找出该区间内的最小素数与最大素数在素数表中的位置,结果即为s[r]-s[l-1]
代码如下：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 10000005
int now,t;
int c[maxn],f[maxn],s[maxn];
bool prime[maxn]; void solve(int x)
{
t=;
int i,j;
for(i=;i<=x;i++)
{
if(!prime[i])
{
prime[i]=true;
f[now]=i;
t+=c[i];
// s[i]+=c[i];
for(j=i+i;j<=x;j+=i)
{
prime[j]=true;
t+=c[j];
}
s[now]=t;
now++;
}
}
} int lfind(int x)//找大于等于x的最小值
{
int l=,r=now-,mid;
while(l<=r)
{
mid=(l+r)/;
if(f[mid]>=x)
{
r=mid-;
}
else
l=mid+;
}
return l;
} int rfind(int x)//找小于等于x的最大值
{
int l=,r=now-,mid;
while(l<=r)
{
mid=(l+r)/;
if(f[mid]<=x)
l=mid+;
else
r=mid-;
}
return r; }
int main()
{
int n,x;
scanf("%d",&n);
int Max=;
now=;
memset(prime,false,sizeof(prime));
memset(c,,sizeof(c));
memset(f,,sizeof(f));
memset(s,,sizeof(s));
for(int i=;i<n;i++)
{
scanf("%d",&x);
if(x>Max)
Max=x;
c[x]++;
}
solve(Max);
int m,l,r;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&l,&r);
int t1=lfind(l);
int t2=rfind(r);
// cout<<t1<<' '<<t2<<endl;
// cout<<f[t1]<<' '<<f[t2]<<endl;
if(t1==)
{
printf("%d\n",s[t2]);
}
else
printf("%d\n",s[t2]-s[t1-]);
} return ;
}