给出一个有n个数的序列和m次查询，m次查询给出一个区间，求区间中素数的函数值f（p）之和。f(p)表示能序列中能整除p的元素个数。
线性筛出素数，在筛选素数的同时，处理f(p)。采用线性筛素数就能得出每个素数是序列中哪几个数字的倍数。一举两得，再使用前缀和处理一下。得到答案。
代码:
#include<iostream> #include<string> #include<cstring> using namespace std; const int N=10000010; int n,m,l,r,prime[N],f[N],s[N]; void Init(){ int i,j; memset(prime,0,sizeof(prime)); memset(f,0,sizeof(f)); memset(s,0,sizeof(s)); cin>>n; for(i=0;i<n;++i){ int tmp; cin>>tmp; s[tmp]++; } //打表 处理f(p) for(i=2;i<N;++i){ if(prime[i])continue; for(j=i;j<N;j+=i){ //s[j]如果不为0 说明序列中有元素值为j，并且j还是素数i的倍数，f(i)+=s[j]，就能得到f(p); if(s[j])f[i]+=s[j]; prime[j]=1; } } //前缀和处理 for(i=2;i<=N;++i)f[i]+=f[i-1]; } void solve(){ cin>>m; for(int i=1;i<=m;++i){ cin>>l>>r; if(l>N)l=N; if(r>N)r=N; cout<<f[r]-f[l-1]<<endl; } } int main() { ios::sync_with_stdio(false); Init(); solve(); return 0; }