题意：给你一个n，输入n个数，然后输入m，接下来有m个询问，每一个询问为[l,r]，然后输出在区间内[l,r]内f(p)的和，p为[l,r]的素数，f(p)的含义为在n个数中是p的倍数的个数。
思路：先打出10000000内的素数，然后统计每一个素数在n个数中的倍数的个数记录在num[i]中，在每次询问的是找出l，r在素数表的位置,然后计算就可以。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10000100
using namespace std; int n,m,cnt;
int x[maxn];
bool vis[maxn];
int vis1[maxn];
int f[maxn];
int l[maxn],r[maxn];
int num[maxn];
int sum[maxn]; void Getprime()
{
cnt=;
vis[]=vis[]=true;
memset(vis,false,sizeof(vis));
for(int i=; i<=maxn; i++)
{
if(!vis[i])
{
f[cnt++]=i;
for(int j=*i; j<=maxn; j+=i)
{
vis[j]=true;
}
}
}
} int main()
{
Getprime();
while(scanf("%d",&n)!=EOF)
{
memset(vis1,,sizeof(vis1));
int max1=;
for(int i=; i<n; i++)
{
scanf("%d",&x[i]);
vis1[x[i]]++;
max1=max(max1,x[i]);
}
for(int i=; i<cnt; i++)
{
for(int j=f[i]; j<=max1; j+=f[i])
{
if(vis1[j])
{
num[f[i]]+=vis1[j];
}
}
}
memset(sum,,sizeof(sum));
for(int i=; i<cnt; i++)
{
if(i==)
{
sum[i]=num[f[i]];
}
else
{
sum[i]=sum[i-]+num[f[i]];
} }
scanf("%d",&m);
for(int i=; i<=m; i++)
{
scanf("%d%d",&l[i],&r[i]);
if(l[i]>)
{
printf("0\n");
continue;
}
int ll=lower_bound(f,f+cnt,l[i])-f;
int rr=lower_bound(f,f+cnt,r[i])-f;
if(f[cnt-]<=r[i])
{
rr=cnt-;
}
if(f[ll]>r[i])
{
printf("0\n");
continue;
}
if(f[rr]>r[i])
{
rr=rr-;
}
if(l[i]==r[i])
{
printf("%d\n",num[l[i]]);
}
else
printf("%d\n",sum[rr]-sum[ll-]);
}
}
return ;
}