数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[擂台] 快速求出10^12以内回文素数

[复制链接]
 楼主| 发表于 2008-3-31 09:24:03 | 显示全部楼层
本来就没有么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 11:24:30 | 显示全部楼层
10^12内回文素数表

Prime Palindromes.rar

144.52 KB, 下载次数: 34, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 11:29:35 | 显示全部楼层
2,3,5,7,11这些显然的回文素数就没写在里面了.总共是47990个..
数据可能有误,还麻烦哪位检验一下
感觉这个题,就算计算10^14以内的回文素数,在1秒内出解也是很困难的,更不用说10^16了.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-2 11:35:57 | 显示全部楼层
代码呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 11:36:57 | 显示全部楼层
我写不出汇编的.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-2 11:45:35 | 显示全部楼层
C足够了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 12:08:34 | 显示全部楼层
计算10^16以内的回文素数,我们需要先计算出10^8以内的所有素数(实际上sqrt(2)*10^7就可以了),这部分工作量现在的计算机应该是没有问题的。
然后余下的问题就是如何筛选10^15以内所有奇数位长的回文素数。如果简单一个个回文数同所有10^8以内的素数相除,那肯定速度不行。所以必须设计一个有效的筛选法才行。不过这个肯定有难度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 13:39:23 | 显示全部楼层
判素的问题,我用的是特殊底的miller-rabin测试,只要通过该测试,可以保证是素数。
我现在觉得最难的还是侯选的回文素数太多了,我虽然考虑了剔除整除2,3,5,11的数,但侯选数还是太多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-2 13:44:28 | 显示全部楼层
那你筛的素数太少
至少要筛到10000以内才好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-2 13:47:36 | 显示全部楼层
ls的话没看懂,解释一下啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-5-16 12:33 , Processed in 0.112656 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表