学步园

/*  
* 程序的版权和版本声明部分:  
* Copyright (c) 2013，郑州大学SIAS国际学院    
* 作    者：  王  杰
* 完成日期：2013 年 11 月 9 日  
*  
* 对任务及求解方法的描述部分:
* 输入描述： 略或见注释、总结
* 问题描述： 略或见注释、总结
* 程序输出： 略或见注释、总结
* 问题分析： 略或见注释、总结
* 算法设计： 略或见注释、总结
*/

#include<stdio.h>  

int prime(int n)
{
	int i;
	if(n<2) return 0;
	for(i=2;i*i<=n;i++)
		if(n%i==0) return 0;
	return 1;
}
 
int main()  
{  
    int n;      //组数  
    int x;      //测试数据  
    int z,m;        //左边最接近的素数，右边最接近的素数  
    int ly,lz;      //右边的最接近的素数的与x的距离，左边的最接近的素数的与x的距离  
    int q;      //为了保存输入的x的值，在做完向左查找后，初始化x，继续做向右查找  
    scanf("%d",&n);  
    while(n--){  
        scanf("%d",&x);  
        q=x; 
        if(x==1)        //x=1时的特殊情况，单独列出来  
            printf("2 1\n");        
        else if(prime(x))  
            printf("%d 0\n",x);  
        else{  
            do{  
                z=--x;  
                if(prime(z)){  
                    lz=q-z;     //这里是q-z，不能是x-z  
                    break;  
                }  
            } while(1);  
                  
            x=q;        //初始化x  
            do{  
                m=++x;  
                if(prime(m)){  
                    ly=m-q;     //这里是m-q，不能是m-x  
                    break;  
                }  
            } while(1);  
        if(lz<=ly)  
            printf("%d %d\n",z,lz);  
        else  
            printf("%d %d\n",m,ly);     
        }  
          
    }  
    return 0;  
}

运行结果：

总结：第一次碰见超时问题。自定义的函数效率有点低，后来改进了一下，提高了效率，问题就解决了。恩，这次最大的感受就是程序的效率问题很重要！

附上代码对比一下：

//效率较低的：
int prime(int n) 
{ 
	int a=2;                    //当n为1时没有考虑到 
	while (a<=n) 
	    if (!(n%a++)) 
	        break; 
	if(a==n+1 && n!=1)  
	    return 1; 
	return 0; 
}

//效率较高的：
int prime(int n)
{
	int i;                     
	if(n<2) return 0;          //n为1时考虑到了
	for(i=2;i*i<=n;i++)
		if(n%i==0) return 0;
	return 1;
}

//效率更高一点的：
#include<math.h>
int prime(int n)
{
	int mMax=sqrt(n);
	for(int i=2;i<=mMax;i++)
		if(n % i==0) return false;
	return true; 
}

现在才是有了一种体会：程序的效率真的很重要，比如：上面的函数，如果测试数据较大，比如是十亿级别的，程序就得反应几秒钟（3秒左右吧）；下面的函数，同样是十亿级别的，反应时间人基本上感觉不到。这就是程序的效率问题！