素数问题

筛选素数先建一个小素数表 2-sqrt（max) 再根据这个表来进行区间素数的筛选
View Code
 1 #include<math.h>
 2 #include<stdio.h>
 3 #include<string.h>
 4 __int64 x[1000011];
 5 int pr[46500],pd[46500],pg[1000011];
 6 int main()
 7 {
 8     __int64  n,m,x1,x2,x3,x4,y;
 9     int i,j,k;
10     for(i = 2 ; i <= 46500 ; i++)
11     {
12         if(!pr[i])
13         {
14             for(j = i+i ; j <= 46500 ; j+=i)
15             if(pr[j])
16             pr[j] = 1;
17         }
18     }
19     int g = 0;
20     for(i = 2 ; i <= 46500 ; i++)
21     if(!pr[i])
22     pd[g++] = i;
23     while(scanf("%I64d%I64d",&n,&m)!=EOF)
24     {
25         memset(pg,0,sizeof(pg));
26         k = 0;
27         for(i = 0 ;i < g ; i++)
28         {
29             if(n%pd[i])
30             y = n/pd[i]+1;
31             else
32             y = n/pd[i];
33             if(n<=pd[i])
34             y++;
35             for(j = y*pd[i]-n ; j <= m-n ; j+=pd[i])
36             if(!pg[j])
37                 pg[j] = 1;
38         }
39         if(n==1)
40             pg[0] = 1;
41         k = 0;
42         for(i = 0 ; i <= m-n ; i++)
43         if(!pg[i])
44         {
45             x[k++] = i+n;
46         }
47         if(k>1)
48         {
49             __int64 min = x[1]-x[0],max=0;
50             x3 = x[0];
51             x4 = x[1];
52             for(i = 1 ;i <k ; i++)
53             {
54                 if(x[i]-x[i-1]>max)
55                 {
56                     max = x[i]-x[i-1];
57                     x2 = x[i];
58                     x1 = x[i-1];
59                 }
60                 if(x[i]-x[i-1]<min)
61                 {
62                     min = x[i]-x[i-1];
63                     x4 = x[i];
64                     x3 = x[i-1];
65                 }
66             }
67             printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",x3,x4,x1,x2);
68         }
69         else
70         printf("There are no adjacent primes.\n");
71     }
72     return 0;
73 }