1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| int n;
int pri[maxn];
int vis[maxn];
ll le, ri;
int not_pri[maxn];
int pri_cnt;
void get_prime_between_le_and_ri() {
REP(i,0,pri_cnt) {
ll g = le / pri[i];
while(g<=1) {
g++;
}
for(ll j=g*pri[i];j<=ri;j+=pri[i]) {
if(j>=le) {
not_pri[j-le] = 1;
}
}
}
if(le == 1) {
not_pri[0] = 1;
}
}
int v[maxn];
void solve() {
int up = 5e4;
pri_cnt = 0;
REPP(i,2,up) {
if(!vis[i]) {
pri[pri_cnt] = i;
pri_cnt++;
}
for(int j=i;j<=up;j+=i) {
vis[j] = 1;
}
}
while(scanf("%lld%lld", &le, &ri) != -1) {
memset(not_pri, 0, sizeof(not_pri));
get_prime_between_le_and_ri();
int cnt = 0;
REP(i,0,ri-le+1) {
if(not_pri[i] == 0) {
v[cnt] = i + le;
cnt++;
}
}
if(cnt <= 1) {
puts("There are no adjacent primes.");
continue;
}
int dismax = 1;
int dismin = 1;
REP(i,1,cnt) {
if(v[i] - v[i-1] > v[dismax] - v[dismax-1]) {
dismax = i;
}
if(v[i] - v[i-1] < v[dismin] - v[dismin-1]) {
dismin = i;
}
}
printf("%d,%d are closest, %d,%d are most distant.\n", v[dismin-1], v[dismin], v[dismax-1], v[dismax]);
}
}
|