题目链接:uva 10140 - Prime Distance
题目大意:给出一个范围,问说该范围内,相邻的两个素数最大距离和最小距离。
解题思路:类似素数筛选法,起始位置有L开始,直到超过R,处理出素数之后就好办了。
#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 1e6;
typedef long long ll;
int cp, v[maxn+5];
ll limit, prime[maxn+5];
void primeTable (int n) {
cp = 0;
memset(v, 0, sizeof(v));
for (int i = 2; i <= n; i++) {
if (v[i])
continue;
prime[cp++] = i;
for (int j = 2 * i; j <= n; j += i)
v[j] = 1;
}
}
inline ll cal(ll a, ll b) {
ll k = b / a;
if (b%a)
k++;
if (k * a <= limit && v[k*a] == 0)
k++;
return k * a;
}
int cnt, set[maxn+5], vis[maxn+5];
ll L, R;
void solve () {
memset(vis, 0, sizeof(vis));
ll m = sqrt(R+0.5);
for (int i = 0; i < cp; i++) {
if (prime[i] > m)
break;
for (ll j = cal(prime[i], L); j <= R; j += prime[i]) {
vis[j-L] = 1;
}
}
cnt = 0;
for (ll i = L; i <= R; i++) {
if (i == 1 || i == 0)
continue;
if (vis[i-L])
continue;
set[cnt++] = i-L;
}
}
int main () {
limit = 1<<16;
primeTable(limit);
while (scanf("%lld%lld", &L, &R) == 2) {
solve();
if (cnt <= 1)
printf("There are no adjacent primes.\n");
else {
int minRec, maxRec, minDis, maxDis;
maxDis = 0;
minDis = 1e7;
for (int i = 1; i < cnt; i++) {
int tmp = set[i] - set[i-1];
if (tmp > maxDis) {
maxDis = tmp;
maxRec = i;
}
if (tmp < minDis) {
minDis = tmp;
minRec = i;
}
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n", set[minRec-1]+L, set[minRec]+L, set[maxRec-1]+L, set[maxRec]+L);
}
}
return 0;
}
分享到:
相关推荐
ACM---算法数论
从整体讲解数论,课程的重点是密码学(对称密码学和非对称密码学)所涉及数学理论和有效算法实现。
大数据-算法-数论中几个著名函数的性质研究.pdf
本资源主要包括信息安全、数论基础在内的整除理论、同余理论等,有一部分初等数论的内容、密码学的内容和近世代数的内容
大数据-算法-数论中一些著名函数及和式算术性质的研究.pdf
我09年参加现场赛前准备的,这些公式有的是在POJ等OJ上做题时遇到的,还有些可能会出现的数学公式,本人非数学出身,准备的内容尚浅,就是多和乱(不敢说丰富)
很好的初等数论的教材,共三卷,这是第二卷
CJ2-07-简单数论-博弈论初步.pdf
C++ J2-04-简单数论-巩固练习.pdf
C语言-02-简单数论-整除那套理论.pdf
蓝桥杯,算法CJ2-03-简单数论-取模那套理论.pdf
在乘法数论中,在素数分解期间,用素数覆盖正整数可能被视为是并行系统的结果,当且仅当素数倒数的乘积的欧拉公式为真时,并行系统才能正常运行。 给出了质数小于或等于任意界限的精确公式。 可以使用Wolfram的...
大数据-算法-关于数论中一些和式的算术性质研究.pdf
acm-数论 有关数论的一些知识,以及算法实现等。
2009-11数论和密码--南京 不错哦 ~~~~~~~~~~~~~~~~~~~~~~~~~
法兰西数学精品译丛-解析与概率数论导引(中文版)-[法]G·特伦鲍姆-陈华一(译)-高等教育出版社-2011.pdf
代数数论包。Algebraic Number Theory package。
数论是Acm中的重点内容。历年竞赛题目, 一般都有1-2道与数论有密切关系。数论涉及的概念 和算法很多,用途也非常广泛。掌握与数论有关的 方法,是参赛者需要具备的必要技能。
锈数理论 数论中Rust算法的实现。 实现的算法包括: 核因子判别式/多项式的结果例子看一下文件data/input-discriminant.yml 。 # Find the discriminant of 2x^3 + x^2 - 2x + 3.# To feed this file to the ...