24.素数距离问题
发布时间
阅读量：
阅读量
描述
请提供一组数字，并设计一个算法来找出每个整数与其相邻最近的素数，并计算它们之间的距离长度。特别地，在存在等距情况时，请优先选择左侧的那个素数值及其对应的距离作为结果输出。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0。
输入 第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)
输出 每行输出两个整数 A B.
其中 A 代表离相应测试数据最近的素数,B 代表两者之间的距离.
样例输入
样例输出
0<M<1000000,因此需要筛法打表。
陷阱：M的界限是(0,1000000)但相邻素数不一定在这个范围内。
经计算得，所需的最后一个素数是1000003。
代码如下。
#include <stdio.h>
int notPrime[1000004] = { 1, 1 };
void init();
int main() {
int n, distance;
init();
scanf("%d\n", &n);
while (n--) {
int now;
distance = 0;
scanf("%d\n", &now);
while (1) {
if (now - distance > 0 && !notPrime[now - distance])
break;
else if (now + distance < 1000004 && !notPrime[now + distance]) {
distance *= -1;
break;
}
distance++;
}
printf("%d %d\n", now - distance, distance > 0 ? distance : -distance);
}
return 0;
}
void init() {
int i, j;
for (i = 2; i < 1001; i++)
if (notPrime[i])
continue;
else
for (j = i * i; j < 1000004; j += i)
notPrime[j] = 1;
}
AI写代码全部评论 (0)
还没有任何评论哟~