Question

C语言 素数距离问题

/*素数距离问题
时间限制：3000 ms | 内存限制：65535 KB
难度：2
描述
现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0
输入
第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000)，
输出
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。
样例输入
3
6
8
10
样例输出
5 1
7 1
11 1
*/
#include<stdio.h>
#include<math.h>
int f1(int n)//判断是否为素数,返回值为1时为素数，返回值为0是非素数
{
int i;
if(n==1)
return 0;
else{
for(i=2;i<sqrt(n);i++)
if(n%i==0)
return 0;
else if(n%i==1)
return 1;
}
}

int f2(int n)//如果n是素数则返回其本身，如果不是素数，返回距离其最近的值
{
int a,b,i,j;
if(f1(n)==1)
return n;
else if(f1(n)==0)
{
for(i=n;f1(i)==1;i--)
a=i;
for(j=n;f1(j)==1;j++)
b=j;
// x=abs(n-a);
// y=abs(n-b);
if((n-a)>=(b-n))
return b;
else return a;
}
}
int main()
{
int m,i,n;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&n);
printf("%d %d",f2(n),abs(n-f2(n)));
}
printf("\n");
}

求高手指导，问题出在哪里了啊？

Answer 1

#include <stdio.h>
#include<math.h>
int f1(int n)//判断是否为素数,返回值为1时为素数，返回值为0是非素数
{
int i;
if(n==1)
return 0;
else
{
for(i=2;i<=sqrt(n);i++)
if(n%i==0)
return 0;
return 1; //不能用else，必须所有i值都不能整除，才能确定为素数
}
}

int f2(int n)//如果n是素数则返回其本身，如果不是素数，返回距离其最近的值
{
int a,b,i,j;
if(f1(n)==1)
return n;
else
{
for(i=n;f1(i)!=1;i--); //条件为不是素数循环，直到找到素数为止
a=i;
for(j=n;f1(j)!=1;j++);
b=j;
if((n-a)>=(b-n))
return b;
else return a;
}
}
int main()
{
int m,i,n;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&n);
printf("%d %d\n",f2(n),abs(n-f2(n)));
}
printf("\n");
}

Answer 2

一个一个验证效率不高，有可能tle，建议打素数表后再操作。

#include <stdio.h>
#include<math.h>
int f1(int n)
{
int i;
if(n==1)
return 0;
else
{
for(i=2;i<=sqrt(n);i++)//使用“<=”，否则完全平方数就出错
if(n%i==0)
return 0;
return 1; //判断素数必须所有i都不能整除，才能确定为素数（建议看一下基础教程）
}
}

int f2(int n)//如果n是素数则返回其本身，如果不是素数，返回距离其最近的值
{
int a,b,i,j;
if(f1(n)==1)
return n;
else
{
for(i=n;f1(i)!=1;i--); //不是素数就一直循环，直到找到素数为止
a=i;
for(j=n;f1(j)!=1;j++);
b=j;
if((n-a)>=(b-n))
return b;
else return a;
}
}
int main()
{
int m,i,n;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&n);
printf("%d %d\n",f2(n),abs(n-f2(n)));
}
printf("\n");
}

Answer 3

不会

Answer 4

不懂。。