UVA10140 Prime Distance

L, R很大，所以哪怕用线性筛也会T飞的，但是看到R - L不太大，因此我们可以先筛出[1, √R]所有素数，然后用这些数筛出[L, R]的所有合数。具体做法是对于每一个pi，筛去所有的 i * pi （⌈L / i⌉ <= i <= ⌊R / i⌋）。然后遍历[L, R]的所有素数更新答案即可。

要注意的是1不是质数，然后如果素数表拿int存的话，prime[i] * prime[i]要强制转换成long long ，否则爆了后会无限循环然后RE。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<cctype>
 8 #include<vector>
 9 #include<stack>
10 #include<queue>
11 using namespace std;
12 #define enter puts("") 
13 #define space putchar(' ')
14 #define Mem(a, x) memset(a, x, sizeof(a))
15 #define rg register
16 typedef long long ll;
17 typedef double db;
18 const int INF = 0x3f3f3f3f;
19 const db eps = 1e-8;
20 const int maxp = 5e5 + 5;
21 const int maxn = 1e6 + 5;
22 inline ll read()
23 {
24     ll ans = 0;
25     char ch = getchar(), last = ' ';
26     while(!isdigit(ch)) {last = ch; ch = getchar();}
27     while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
28     if(last == '-') ans = -ans;
29     return ans;
30 }
31 inline void write(ll x)
32 {
33     if(x < 0) x = -x, putchar('-');
34     if(x >= 10) write(x / 10);
35     putchar(x % 10 + '0');
36 }
37 
38 ll L, R;
39 int prime[maxp], v[maxp];
40 bool vis[maxn];
41 
42 void init()
43 {
44     for(int i = 2; i < maxp; ++i)
45     {
46         if(!v[i]) v[i] = i, prime[++prime[0]] = i;
47         for(int j = 1; j <= prime[0] && prime[j] * i <= maxp; ++j)
48         {
49             if(prime[j] > v[i]) break;
50             v[i * prime[j]] = prime[j];        
51         }
52     }
53 }
54 
55 int main()
56 {
57     init();
58     while(scanf("%lld%lld", &L, &R) != EOF)
59     {
60         Mem(vis, 0); if(L == 1) vis[0] = 1;
61         for(int i = 1; (ll)prime[i] * (ll)prime[i] <= R && i <= prime[0]; ++i)
62         {
63             for(int j = (L + prime[i] - 1) / prime[i]; j <= R / prime[i]; ++j)
64                 if(j > 1) vis[j * prime[i] - L] = 1;
65         }
66         ll Min1 = 0, Min2 = 0, Max1 = 0, Max2 = 0, now1 = 0, now2 = 0;
67         for(int i = 0; i <= R - L; ++i)
68         {
69             if(!vis[i]) 
70             {
71                 now1 = now2; now2 = i + L;
72                 if(now1)
73                 {
74                     if(!Min1 || now2 - now1 < Min2 - Min1) Min1 = now1, Min2 = now2;
75                     if(!Max1 || now2 - now1 > Max2 - Max1) Max1 = now1, Max2 = now2;
76                 }
77             }
78         }
79         if(!Min1) printf("There are no adjacent primes.
");
80         else printf("%lld,%lld are closest, %lld,%lld are most distant.
", Min1, Min2, Max1, Max2);
81     }
82     return 0;
83 }

View Code