1 条题解
-
0
#include<bits/stdc++.h>//这是100分代码 using namespace std; typedef long long LL; int prime[1110000], pr, a[1110000], alen;bool v[1110000]; int main() { pr=0;memset(v,0,sizeof(v)); for(int i=2;i<=50000;i++) { if(v[i]==0)prime[++pr]=i; for(int j=1;j<=pr && i*prime[j]<=50000;j++) { v[i*prime[j]]=1; if(i%prime[j]==0) break; } } int l, r; while(scanf("%d%d", &l, &r)!=EOF) { //把[l,r]区间内所有的合数用他们的最小质因子筛掉 memset(v, 0, sizeof v); for (int i = 1; i <= pr;i++) { LL p = prime[i];//(l + p - 1)也有可能超过int for(LL j = max(2 * p, (l + p - 1) / p * p); j <= r; j += p)//最后一个j有可能超过int v[j - l] = 1; } //剩下的所有的都是素数了 alen = 0; for (int i = 0; i <= r - l; i++ ) if (!v[i] && i + l > 1) a[++alen] = i + l; if (alen < 2) printf("There are no adjacent primes.\n"); else { //计算间隔 int minp = 1, maxp = 1; for (int i = 1; i < alen;i++) { int d = a[i + 1] - a[i]; if (d < a[minp + 1] - a[minp]) minp = i; if (d > a[maxp + 1] - a[maxp]) maxp = i; } printf("%d,%d are closest, %d,%d are most distant.\n", a[minp], a[minp + 1], a[maxp], a[maxp + 1]); } } return 0; }
- 1
信息
- ID
- 1305
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 185
- 已通过
- 47
- 上传者