可以证明: 除了11,不存在偶数位的素数回文数
so,qq95620412的代码还可以优化,另外,素数判断的代码还可以进一步优化.
可以证明给我看看吗？
----------------解决方案--------------------------------------------------------
可以证明给我看看吗？
偶数位的回文数都能被11除。
你可以把每个偶数为的回文数除以 11
101101 / 11 == 9191;
或你看看你的那个程序生成的回文数，素数偶数位回文只有 11 。
你的程序很好
[此贴子已经被作者于2007-11-9 18:00:51编辑过]
----------------解决方案--------------------------------------------------------
long int nexthuiwen(long int currenthuiwen)
//输入：一个回文数
//输出：比当前回文数大的最小回文数
{
long int i=currenthuiwen,m;
int weishu=0; //数字的位数
long int j=0;
// printf("当前回文数是：%ld\n",i);
while(i>0) //求出数值的位数
{
i=i/10;
weishu+=1;
}
if(weishu==1) //求出规整前的新数
{
currenthuiwen+=1;
}
else
{
currenthuiwen+=pow10(weishu/2);
currenthuiwen=currenthuiwen-currenthuiwen%pow10(weishu/2);
}
// printf("新数为:%ld\n",currenthuiwen);
i=currenthuiwen; //求出规整前数值的位数
weishu=0;
while(i>0)
{
i=i/10;
weishu+=1;
}
for(j=1;j<=weishu/2;j++) //规整新数
{
m=currenthuiwen/(long int)pow10(weishu-j)%10*(long int)pow10(j-1);
// printf("%ld\n",m);
currenthuiwen+=m;
}
// printf("新的回文数是: %ld\n",currenthuiwen);
return currenthuiwen;
}
有人能给出这个函数是如何计算下一个回文数的吗？
看不懂啊。
----------------解决方案--------------------------------------------------------
#include<stdio.h>
#include<math.h>
#include<time.h>
#define MAX 1000000000
#define MIN 101 //最小的3为回文数
long int pow10(int i)
{
long int result=1;
while(i>0)
{
result*=10;
i--;
}
return result;
}
long int nexthuiwen(long int currenthuiwen)
//输入：一个回文数
//输出：比当前回文数大的最小回文数
{
long int i=currenthuiwen,m;
int weishu=0; //数字的位数
long int j=0;
// printf("当前回文数是：%ld\n",i);
while(i>0) //求出数值的位数
{
i=i/10;
weishu+=1;
}
if(weishu==1) //求出规整前的新数
{
currenthuiwen+=1;
}
else
{
currenthuiwen+=pow10(weishu/2);
currenthuiwen=currenthuiwen-currenthuiwen%pow10(weishu/2);
}
// printf("新数为:%ld\n",currenthuiwen);
i=currenthuiwen; //求出规整前数值的位数
weishu=0;
while(i>0)
{
i=i/10;
weishu+=1;
}
for(j=1;j<=weishu/2;j++) //规整新数
{
m=currenthuiwen/(long int)pow10(weishu-j)%10*(long int)pow10(j-1);
// printf("%ld\n",m);
currenthuiwen+=m;
}
// printf("新的回文数是: %ld\n",currenthuiwen);
return currenthuiwen;
}
long int nexthuiwen_youhua(long int currenthuiwen)
//声明：按cosdos Eastsun版主的建议，将函数功能进行适当修改，以减少运行时间
//输入：一个位数为奇数的奇数回文数
//输出：比当前回文数大的位数为奇数的最小奇数回文数
//例如：19291 ->19391 39993->50005 99999->1000001
//编程思路： 1.先求出原回文数的位数 如：19291的位数为5
// 2.将回文数的最中间位数的数值加1 即 39993->40093,若新数为偶数位数，则乘以10 ,若首位为偶，则首位+1,得到规整前的新数
// 3.规整新数，将新数的右对称分支改为0 即 40093->40000
// 4.求出新数的右对称分支，加到该数上 即 40000->40004
// 5.返回新的回文值
{
long int i=currenthuiwen,m;
int weishu=0; //数字的位数
long int j=0;
// printf("当前回文数是：%ld\n",i);
while(i>0) //求出数值的位数
{
i=i/10;
weishu+=1;
}
if(weishu==1) //求出规整前的新数
{
currenthuiwen+=1;
}
else
{
currenthuiwen+=pow10(weishu/2);
currenthuiwen=currenthuiwen-currenthuiwen%pow10(weishu/2);
}
i=currenthuiwen; //求出规整前数值的位数
weishu=0;
while(i>0)
{
i=i/10;
weishu+=1;
}
if(weishu%2==0) //若位数为奇数，则 *10
{ currenthuiwen*=10;
weishu++;
}
if(currenthuiwen/pow10(weishu-1)%2==0) //若首位是偶数，则首位+1
{
currenthuiwen+=pow10(weishu-1);
}
// printf("规整前新数为:%ld\n",currenthuiwen);
for(j=1;j<=weishu/2;j++) //规整新数
{
m=currenthuiwen/(long int)pow10(weishu-j)%10*(long int)pow10(j-1);
// printf("%ld\n",m);
currenthuiwen+=m;
}
// printf("新的回文数是: %ld\n",currenthuiwen);
return currenthuiwen;
}
int sushu_youhua(long int data)
//声明：按cosdos Eastsun版主的意思，进行了优化
//输入：任意非偶长整数
//输出：若该整数为素数，则输出1，否则输出0
{
long int end=(long int)sqrt(data);
long int i;
for(i=3;i<=end;i+=2) //读者可以考虑以下为什么不写成 i++
{
if(data%i==0)return 0;
}
return 1;
}
int main(void)
{
long int data=MIN;
clock_t start,end;
start=clock();
printf("3\n5\n7\n11\n");
while(data<=MAX)
{
if(sushu_youhua(data))
{
printf("%ld\n",data);
}
data=nexthuiwen_youhua(data);
}
end=clock();
printf("%lf\n",(double)((end-start)/CLOCKS_PER_SEC));
getchar();
return 0;
}
[此贴子已经被作者于2007-11-10 20:13:19编辑过]
----------------解决方案--------------------------------------------------------
运行了一下
输出到屏幕时 2秒
输出到文件时 0秒
----------------解决方案--------------------------------------------------------
呵呵,不错~
----------------解决方案--------------------------------------------------------