快速求出10^12以内回文素数

无心人 · 发表于 2008-3-31 09:24:03

本来就没有么

medie2005 · 发表于 2008-4-2 11:24:30

10^12内回文素数表

medie2005 · 发表于 2008-4-2 11:29:35

2,3,5,7,11这些显然的回文素数就没写在里面了.总共是47990个.. 数据可能有误,还麻烦哪位检验一下感觉这个题,就算计算10^14以内的回文素数,在1秒内出解也是很困难的,更不用说10^16了.

无心人 · 发表于 2008-4-2 11:35:57

代码呢？

medie2005 · 发表于 2008-4-2 11:36:57

我写不出汇编的.

无心人 · 发表于 2008-4-2 11:45:35

C足够了

mathe · 发表于 2008-4-2 12:08:34

计算10^16以内的回文素数，我们需要先计算出10^8以内的所有素数(实际上sqrt(2)*10^7就可以了)，这部分工作量现在的计算机应该是没有问题的。然后余下的问题就是如何筛选10^15以内所有奇数位长的回文素数。如果简单一个个回文数同所有10^8以内的素数相除，那肯定速度不行。所以必须设计一个有效的筛选法才行。不过这个肯定有难度

medie2005 · 发表于 2008-4-2 13:39:23

判素的问题，我用的是特殊底的miller-rabin测试，只要通过该测试，可以保证是素数。我现在觉得最难的还是侯选的回文素数太多了，我虽然考虑了剔除整除2，3，5，11的数，但侯选数还是太多。

无心人 · 发表于 2008-4-2 13:44:28

那你筛的素数太少至少要筛到10000以内才好

medie2005 · 发表于 2008-4-2 13:47:36

ls的话没看懂，解释一下啊

账号		自动登录	找回密码
密码			欢迎注册

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