题目链接：
codeforces 385C
题目大意：
给出n个数，数据范围的个数。
题目分析：
直接线性筛素数，记录每个数最大的素因数，然后统计对于每个素因数对应的，然后求取前缀和，，来方便求取区间和。
AC代码：#include <cstdio>const int N=10000001;int p[N],pn;int mpf[N];int sum[N];void init() {for (int i=2;i<N;i++) {if (mpf[i]==0) mpf[i]=p[pn++]=i;for (int j=0;j<pn&&i*p[j]<N&&p[j]<=mpf[i];j++)mpf[i*p[j]]=p[j];}}int main() {init();int n;scanf(“%d”,&n);while (n–) {int x;scanf(“%d”,&x);while (x!=1) {int t=mpf[x];sum[t]++;while (x%t==0) x/=t;}}for (int i=1;i<N;i++) sum[i]+=sum[i-1];scanf(“%d”,&n);while (n–) {int l,r;scanf(“%d%d”,&l,&r);if (l>=N) printf(“%d\n”,0);else if (r>=N) printf(“%d\n”,sum[N-1]-sum[l-1]);else printf(“%d\n”,sum[r]-sum[l-1]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
仿佛松树就是一位威风的将军，守护着国家的国民。
