题意：给你一个n，输入n个数，然后输入m，接下来有m个询问，每一个询问为[l,r]，然后输出在区间内[l,r]内f(p)的和，p为[l,r]的素数，f(p)的含义为在n个数中是p的倍数的个数。
思路：先打出10000000内的素数，然后统计每一个素数在n个数中的倍数的个数记录在num[i]中，在每次询问的是找出l，r在素数表的位置,然后计算就可以。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 10000100 5 using namespace std; 6 7 int n,m,cnt; 8 int x[maxn]; 9 bool vis[maxn]; 10 int vis1[maxn]; 11 int f[maxn]; 12 int l[maxn],r[maxn]; 13 int num[maxn]; 14 int sum[maxn]; 15 16 void Getprime() 17 { 18 cnt=0; 19 vis[0]=vis[1]=true; 20 memset(vis,false,sizeof(vis)); 21 for(int i=2; i<=maxn; i++) 22 { 23 if(!vis[i]) 24 { 25 f[cnt++]=i; 26 for(int j=2*i; j<=maxn; j+=i) 27 { 28 vis[j]=true; 29 } 30 } 31 } 32 } 33 34 int main() 35 { 36 Getprime(); 37 while(scanf("%d",&n)!=EOF) 38 { 39 memset(vis1,0,sizeof(vis1)); 40 int max1=0; 41 for(int i=0; i<n; i++) 42 { 43 scanf("%d",&x[i]); 44 vis1[x[i]]++; 45 max1=max(max1,x[i]); 46 } 47 for(int i=0; i<cnt; i++) 48 { 49 for(int j=f[i]; j<=max1; j+=f[i]) 50 { 51 if(vis1[j]) 52 { 53 num[f[i]]+=vis1[j]; 54 } 55 } 56 } 57 memset(sum,0,sizeof(sum)); 58 for(int i=0; i<cnt; i++) 59 { 60 if(i==0) 61 { 62 sum[i]=num[f[i]]; 63 } 64 else 65 { 66 sum[i]=sum[i-1]+num[f[i]]; 67 } 68 69 } 70 scanf("%d",&m); 71 for(int i=1; i<=m; i++) 72 { 73 scanf("%d%d",&l[i],&r[i]); 74 if(l[i]>10000000) 75 { 76 printf("0 "); 77 continue; 78 } 79 int ll=lower_bound(f,f+cnt,l[i])-f; 80 int rr=lower_bound(f,f+cnt,r[i])-f; 81 if(f[cnt-1]<=r[i]) 82 { 83 rr=cnt-1; 84 } 85 if(f[ll]>r[i]) 86 { 87 printf("0 "); 88 continue; 89 } 90 if(f[rr]>r[i]) 91 { 92 rr=rr-1; 93 } 94 if(l[i]==r[i]) 95 { 96 printf("%d ",num[l[i]]); 97 } 98 else 99 printf("%d ",sum[rr]-sum[ll-1]); 100 } 101 } 102 return 0; 103 }