求生成回文素数高效算法（c语言）

2009-11-06 13:26:40 来自: 酷虾

如题：指定正整数区间（a，b）求区间中的所有的回文素数！
因为问题规模较大我的算法很慢，忘各位兄弟姐妹帮忙给出一个高效的算法！
小弟跪谢！！！

2009-11-06 13:41:08 IT小兵 (兵哥出手，沙发我有！！)

去有个国外网站下载素数表，然后挨个看回不回

> 删除
2009-11-06 13:53:43 酷虾

这个怎么能行呢，如果可以的话我早就这样做了！
我不需要代码只需要思想就行！
不过还是谢谢小兵了！

> 删除
2009-11-06 14:18:47 IT小兵 (兵哥出手，沙发我有！！)

那你先说说你的算法，我们看看有木有改进的地方

> 删除
2009-11-07 12:02:58 鱿鱼 (地上走的)

百度上有啊···http://zhidao.baidu.com/question/123656956.html
大概的想法就是判断输入的较小数a是不是奇数，如果是偶数就加个1，之后在main循环里每次加2，这样就能节省好多次运算。然后在判断回文的函数里面用一个循环把原来的数变成高位跟低位互换的数，比如123变成321，之后判断是否跟原来的数相同。值得注意的是（对我来说哈）
do
{
n*=10;
n+=num%10;
num/=10;
}
while (num>0);
这一段代码我觉得写得不错，由于num是long型的，当num为一位数时，再自除10这时num就等于0，所以没有多少没用的算法。
判断素数的函数里面只要注意原来的数除以的数除到原来的数的开方就行，也能节省点运算。
菜鸟一个，还请下面的大牛指教~

> 删除
2009-11-07 13:20:41 IT小兵 (兵哥出手，沙发我有！！)

回文当然是构造的而不是判断出来的。
判断回文是不是质数之前做剔除，我能想到的是

个位数是0、2、4、5、6、8
各位数字之和被3整除
各位数字之和不能被3整除 && 个位数是1、3、7、9
位数为偶且位数>2的

我觉能剔掉7/8吧...

> 删除
2009-11-07 13:21:09 IT小兵 (兵哥出手，沙发我有！！)

有补充的没？

> 删除
2009-11-07 15:24:49 鱿鱼 (地上走的)

哦···的确还可以简化好多···

> 删除
2009-11-07 16:24:28 刚一 (变才是不变的)

素数
回文数
回文素数！！！！！！！！

> 删除
2009-11-07 17:26:02 IT小兵 (兵哥出手，沙发我有！！)

回文数
素数
回文素数！！！！！！！！

> 删除
2009-11-07 19:36:26 某因幡 (始動中。。。|「新」)

话说你要这个干什么，能被N整除的数有关于N的公式的，数论我忘了，还有素数的判别那不是一般的花时间啊感觉

> 删除
2009-11-07 20:16:30 酷虾

抱歉，我这几天没上网！
看到大家的回复很感动啊！
我先把我的算法说一下吧！
首先，构造回文：
一.用log10判断出上下限a,b的位数m,n.求出m/2位数的最小值min和n/2位数的最大值max；初始化回文数组p
二.（1）若m/2为偶数则min=min+1,否则继续下一步
（2）求出数min的各个位上的数如123就求出1,2,3.判断最高位的数是否为1,3,7,9, 为真则进行下一步否则跳到4执行
(3) 把a的最高的m-1位逆置（123，逆为21）然后组成回文数pal（12321）,若pal<a或pal>b,直接下一步，反之将pal存入数组p保存后继续下一步
(4)调用二
然后再判断p中的数是否是素数。
判断素数我是看数A开平方后的结果设为a，然后看2-a之间有没有能整除A的数存在，很简单的方法，但是比较繁琐。
而且，上面的回文数生成法也很繁琐，希望大家能够批评指正，帮我完善一下！
再次感谢大家！！！

> 删除
2009-11-07 20:34:57 刚一 (变才是不变的)

2009-11-07 17:26:02 IT小兵 (山寨coder闭门造车ing~) 回文数
素数
回文素数！！！！！！！！

————————————————————
模仿我干嘛？？
你太没个性了

> 删除
2009-11-07 20:39:22 酷虾

2009-11-07 13:20:41 IT小兵 (山寨coder闭门造车ing~)

回文当然是构造的而不是判断出来的。
判断回文是不是质数之前做剔除，我能想到的是

个位数是0、2、4、5、6、8
各位数字之和被3整除
各位数字之和不能被3整除 && 个位数是1、3、7、9
位数为偶且位数>2的

我觉能剔掉7/8吧...
--------------------------------------------------------------------------
我觉的确实没有别的了。感谢！

> 删除
2009-11-07 21:25:49 lzonline01

先构造素数，然后在判断是否为质数，

> 删除
2009-11-07 21:36:20 lzonline01

#include <stdio.h>
#include <math.h>

int Prime(long int w)
{

int a, b,c;
a = w%2;
b=3;
c=(int)sqrt(w);
while (a&&b<=c)
{
a=w%b;
b+=2;
}
return a;
}

int main()
{
int a,b,c,d,e;
int m,n;
long int w;
scanf("%d%d",&m,&n);
a=0;
b=0;
c=0;
d=0;
e=4;
while (a<=9)
{
e++;
if (e==10)
{
e=0;
d++;
}

if (d==10)
{
d=0;
c++;
}

if (c==10)
{
c=0;
b++;
}

if (b==10)
{
b=0;
a++;
}

w=a*100000000+b*10000000+c*1000000+d*100000+e*10000+d*1000+c*100+b*10+a;
while (w%10==0)
{
w=w/10;
}
if( w >= m && w < n ) {
if (Prime(w))
{
printf("%ld\n",w);
if (w>5&&w<100)
{
printf("11\n");
}
}
}
}
return 0;
}

> 删除
2009-11-07 21:38:34 xx (啊呜～)

2009-11-07 21:25:49 lzonline01

先构造素数，然后在判断是否为质数，

素数不就是质数了么……

> 删除
2009-11-07 21:48:21 刚一 (变才是不变的)

好瘦长的代码

> 删除
2009-11-07 23:04:52 CBean (我毫无保留的，面对大自然。。。)

2009-11-07 21:36:20 lzonline01

#include <stdio.h>
#include <math.h>

int Prime(long int w)
{

int a, b,c;
a = w%2;
b=3;
c=(int)sqrt(w);
while (a&&b<=c)
{
a=w%b;
b+=2;
}
return a;

-----------------------------

这代码好骨感 - -！

PS:小兵说的对吧，先构造出回文，再判断素数

> 删除
2009-11-07 23:54:33 Fleurer (白天不懂夜的黑)

大一点的数的素性判定貌似需要用到费马小定理
数不大的话貌似没必要，打个表吧。

> 删除