题意：给定一个数组，求[l,r] 区间，区间里的素数，数组中，能被这个素数整除的个数，再求和。

分析：区间很大，10^9了，找去区间内的素数是不可能的，但是，数组的数很小，而且要能整除区间内的素数，所以，这些很大的素数是没用的，筛出10^7以内的素数就ok了。

怎么算个数呢？

质因数分解，hash一下，再二分区间，应该是很麻烦了，但是网上还有麻烦的，还用到了线段树维护。

 

简单方式是：

将数组hash，在筛素数的时候，检测hash值，是否有这些数，有的话，记录到这个素数中，也就是说，这个数组中，能被这个素数整除的有s个，然后对s求一个前缀和，问题就转换为一个区间和。

 

#include 
      
       using namespace std;//10^7以内的素数const int maxn = 10000000+5;int vis[maxn],g[maxn],s[maxn];int m;int main(int argc, char const *argv[]){    memset(vis,0,sizeof(vis));    memset(g,0,sizeof(g));    memset(vis,0,sizeof(vis));    int n;    scanf("%d",&n);    for(int i=0;i
       
        =maxn) a = maxn-1;        if(b>=maxn) b = maxn-1;        printf("%d\n",s[b]-s[a-1]);    }    return 0;}