题目24: 素数距离问题
描述
现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0
输入
第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)，
输出
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。
样例输入
3
6
8
10样例输出
5 1
7 1
11 1来源
经典题目
[cpp]
/*********************************
* 日期：2013-3-26
* 作者：SJF0115
* 题号: 题目24: 素数距离问题
* 来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=24
* 结果：AC
* 来源：南阳理工OJ
* 总结：
**********************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 1000010
int prime[MAX];
//素数表
void Prime(){
memset(prime,0,sizeof(prime));
for(int i = 2;i < sqrt(MAX)+1;i++){
if(prime[i]){
continue;
}
else{
for(int j = i*i;j < MAX;j += i){
prime[j] = 1;
}
}
}
}
int main()
{
int N,M,LIndex,RIndex;
//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);
Prime();
prime[1] = 1;
prime[0] = 1;
scanf("%d",&N);
//N组测试数据
while(N--){
scanf("%d",&M);
if(prime[M] == 0){
printf("%d 0\n",M);
}
else{
RIndex = M;
LIndex = M;
//寻找左边素数
while(prime[LIndex] == 1 && LIndex >= 0){
LIndex --;
}
//寻找右边素数
while(prime[RIndex] == 1){
RIndex ++;
}
//左边没有找到
if(LIndex < 0){
printf("%d %d\n",RIndex,RIndex-M);
}
//左右都有
else if(M - LIndex <= RIndex - M){
printf("%d %d\n",LIndex,M-LIndex);
}
else{
printf("%d %d\n",RIndex,RIndex-M);
}
}
}
return 0;
}
/*********************************
* 日期：2013-3-26
* 作者：SJF0115
* 题号: 题目24: 素数距离问题
* 来源：http://acm.nyist.net/JudgeOnline/problem.php?pid=24
* 结果：AC
* 来源：南阳理工OJ
* 总结：
**********************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 1000010
int prime[MAX];
//素数表
void Prime(){
memset(prime,0,sizeof(prime));
for(int i = 2;i < sqrt(MAX)+1;i++){
if(prime[i]){
continue;
}
else{
for(int j = i*i;j < MAX;j += i){
prime[j] = 1;
}
}
}
}
int main()
{
int N,M,LIndex,RIndex;
//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);
Prime();
prime[1] = 1;
prime[0] = 1;
scanf("%d",&N);
//N组测试数据
while(N--){
scanf("%d",&M);
if(prime[M] == 0){
printf("%d 0\n",M);
}
else{
RIndex = M;
LIndex = M;
//寻找左边素数
while(prime[LIndex] == 1 && LIndex >= 0){
LIndex --;
}
//寻找右边素数
while(prime[RIndex] == 1){
RIndex ++;
}
//左边没有找到
if(LIndex < 0){
printf("%d %d\n",RIndex,RIndex-M);
}
//左右都有
else if(M - LIndex <= RIndex - M){
printf("%d %d\n",LIndex,M-LIndex);
}
else{
printf("%d %d\n",RIndex,RIndex-M);
}
}
}
return 0;
}
补充：软件开发 , C++ ,
