数论好题
题目要求：求给定序列的素因子如果在给定区间内该数字个数加1;
思路：打表时求出包含给素数因子的数的个数，详见代码 1 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 const int MAX=10000000+10;
6 int vis[MAX],sum[MAX],num[MAX];
7 int main()
8 {
9 int a,l,r,n,m;
10 scanf("%d",&n);
11 memset(vis,0,sizeof(vis));
12 memset(sum,0,sizeof(sum));
13 for(int i=0;i<n;i++)
14 {
15 scanf("%d",&a);
16 num[a]++;
17 }
18 for(int i=2;i<MAX;i++)
19 {
20 if(!vis[i])
21 {
22 for(int j=i;j<=MAX;j+=i)
23 {
24 vis[j]=1;
25 sum[i]+=num[j];
26 }
27 }
28 sum[i]+=sum[i-1];
29 }
30 scanf("%d",&m);
31 for(int i=0;i<m;i++)
32 {
33 scanf("%d %d",&l,&r);
34 l=min(l,MAX-2);
35 r=min(r,MAX-2);
36 printf("%d\n",sum[r]-sum[l-1]);
37 }
38 return 0;
39 }