数论基础小记

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 47000
12 #define M 1000010
13 #define LL long long
14 #define INF 0xfffffff
15 const double eps = 1e-8;
16 const double pi = acos(-1.0);
17 const double inf = ~0u>>2;
18 int p[N],g;
19 LL res[M];
20 bool f[N+10];
21 bool v[M];
22 void init()
23 {
24     int i,j;
25     for(i = 2 ; i<= N ; i++)
26     {
27         if(!f[i])
28         {
29             for(j = i+i ; j <= N;j+=i)
30             f[j] = 1;
31             p[++g] = i;
32         }
33     }
34 }
35 int main()
36 {
37     LL i,j;
38     LL l,u;
39     init();
40     while(scanf("%lld%lld",&l,&u)!=EOF)
41     {
42         memset(v,0,sizeof(v));
43         int o=0;
44         LL y;
45         for(i = 1; i <= g ; i++)
46         {
47            if(l%p[i])
48            {
49                y = (l/p[i]+1)*p[i];
50            }
51            else y = l;
52            for(j = y ; j <= u ; j+=p[i])
53                if(j!=p[i])
54                v[j-l] = 1;
55         }
56         if(l==1) v[0] = 1;
57         for(i = l ; i <= u; i++)
58         if(!v[i-l])
59         {
60             res[++o] = i;
61         }
62         if(o<2)
63         {
64             puts("There are no adjacent primes.");
65             continue;
66         }
67         LL minz=M,st,en,ss,ee,maxz=0;
68         for(i = 1; i < o ; i++)
69         {
70             if(res[i+1]-res[i]<minz)
71             {
72                  minz = res[i+1]-res[i];
73                  st = res[i];
74                  en = res[i+1];
75             }
76             if(res[i+1]-res[i]>maxz)
77             {
78                  maxz = res[i+1]-res[i];
79 
80                  ss = res[i];
81                  ee = res[i+1];
82             }
83         }
84         printf("%lld,%lld are closest, %lld,%lld are most distant.\n",st,en,ss,ee);
85     }
86     return 0;
87 }