能通过2，3，5，7的检验的合数

mathe

由此，我们还是可以以搜索卡米切尔数的代码：http://bbs.emath.ac.cn/viewthrea ... &fromuid=20#pid2131 为基础。只是这里我们有了一个优势，我们可以事先将所有素数分别根据2和3关于它们次数中2的次数分类；只有在两个分类都在一起的那些素数才允许相乘，这样应该可以降低一些复杂度。 但是卡米切尔数的代码中那些$phi(p)=p-1$需要被$phi_{2,3}(p)=LCM(phi_2(p),phi_3(p))$来代替，其中$phi_2(p)$和$phi_3(p)$分别指2和3关于素数p的次数，显然这个数不大于$phi(p)$；而这个部分会导致程序速度比那里慢一些。但是我认为通常$phi_{2,3}(p)$会等于$phi(p)$,所以这里的速度损失应该不大。总体上程序应该比卡米切尔的还要快一些。

无心人

难处理的是双大因子合数

无心人

10000内素数筛选(2,3)的那个表按通过后表长度倒序排列 前面是素数，后面是表长度 7对应的最多 最少几个 (3307,5190),(1117,5182),(61,5168),(13,4884),(5,4603) l10000.txt (14.19 KB, 下载次数: 0)

2008-10-11 16:36 上传

点击文件名下载附件

无心人

过(2,3,5,13)的482个 t23513.txt (7.7 KB, 下载次数: 1)

2008-10-11 16:47 上传

点击文件名下载附件

mathe

原帖由 无心人 于 2008-10-11 15:46 发表 难处理的是双大因子合数

这个好处理，通过中国剩余定理。

无心人

过(2,3,5,13,61)的57个 说明，单纯选最少的几个效果不好

无心人

肚子不会不知道有多少候选素数吧？

mathe

你是说候选伪素数？不知道多少，但是显然挺多的。 不过卡米切尔数的题目可以在3分钟解决到$10^12$,所以如果多花些时间，这个题目解决到$10^16$还是有可能的

medie2005

对测试基(2,3,5,p,q),已经对p,q在10^6内的素数值进行了穷举,得到的结果是: find a better base 13, 31249 fail 39 times find a better base 13, 439883 fail 38 times find a better base 13, 450817 fail 34 times find a better base 569, 655693 fail 33 times find a better base 1747, 16519 fail 32 times find a better base 4057, 696811 fail 30 times 也就是说,当素数表为10^6内时,形如(2,3,5,p,q)的测试基中,最好的是(2,3,5,4057,696811). 这30次误判分别发生在： 1 : 591090138721 2 : 688529415421 3 : 4729662293401 4 : 8649193274551 5 : 34477679139751 6 : 46856248255981 7 : 133157319632851 8 : 153329903387347 9 : 363648418469461 10 : 389503070897221 11 : 583614097586281 12 : 1266147415982707 13 : 1299098974033981 14 : 1406721084285529 15 : 1584266373273781 16 : 1595200878550261 17 : 1806247902316861 18 : 2416612633262101 19 : 2419099357968541 20 : 2818290089448541 21 : 2966288653917847 22 : 3148220891032381 23 : 3533364723868561 24 : 5615477642184301 25 : 6506333961452821 26 : 6576532224211951 27 : 7024865535814141 28 : 7671546758409661 29 : 8723022119133121 30 : 9471030677258041

medie2005

对测试基(2,3,11,p,q),已经对p,q在10^5内的素数值进行了穷举,得到的结果是: 很遗憾,在10^16范围内,竟然没有一组误判次数在40次以下!