论坛 › 算法交流 › 能通过2，3，5，7的检验的合数

medie2005 发表于 2008-10-22 20:24:05

五元组(2，3，5，3586909，5298383) 在10^16内误判25次。
25次误判分别发生在：
1 : 2650618430461
2 : 21378060752641
3 : 156825618585301
4 : 217491152725351
5 : 233040329546641
6 : 489657467586127
7 : 492566766980947
8 : 601103160192727
9 : 663192387663151
10 : 1041459228958501
11 : 1286151751924021
12 : 1806247902316861
13 : 1935283525648021
14 : 2008986405456421
15 : 2435185368202861
16 : 2615594711694667
17 : 3082228476346951
18 : 3330327948852061
19 : 3815693793778901
20 : 6162977935624681
21 : 6657864990136951
22 : 7422283419436621
23 : 8260955971264501
24 : 9772708037810581
25 : 9809214374918701

无心人 发表于 2008-10-23 09:53:53

:)

是否已经搜索完10^7了？

medie2005 发表于 2008-10-23 20:25:57

已经搜完10^7了。25次误判是(2,3,5,p,q)形式的最佳结果。

northwolves 发表于 2008-12-23 00:31:36

强帖留名。花了我近1个小时，累啊。

无心人 发表于 2008-12-23 07:56:46

呵呵

media2005有新进展么?

〇〇 发表于 2009-11-1 18:53:21

数论问题好像计算机也没有什么办法

ssikkiss 发表于 2010-6-10 18:46:58

能不能总结一下，判断2^32内的数是否素数，最好用哪几个测试基？

gxqcn 发表于 2010-6-11 07:40:54

能不能总结一下，判断2^32内的数是否素数，最好用哪几个测试基？
ssikkiss 发表于 2010-6-10 18:46 http://bbs.emath.ac.cn/images/common/back.gif

2^32 内的素数用试除法也很快，最多仅需 $pi(2^16)=6542$ 次即可。
如果要用Miller-Rabin判定，建议可用 {2, 7, 61} 组合测试基。

无心人 发表于 2010-6-11 08:57:29

试除法也有一点点弊端，要占用点内存空间
不知道诸位谁有兴趣，把打包的65536内的素数表
和解包算法发出来

要求是打包的越短越好，解包也要速度快才好
由于解包是顺序解包，也不限定一些高压缩方案

qianyb 发表于 2010-6-11 09:35:52

这个就是以前gxqcn提过的分组方法啊

查看完整版本: 能通过2，3，5，7的检验的合数