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

无心人 发表于 2008-10-9 20:26:29

对于穷举合适的基
以100万内素数为基准
首先分别对5，7使用2，3的小于10^16的表
筛选得到哦表T5, T7
假设表长度为L5, L7
以T5为例
对其余素数依次筛选T5
得到的表以T5表为基准做位组合
通过的记1，失败的记0
则显然，位组合的长度最大(L5 / 8192) KB
得到的数据最大是(L5 / 8192)* Pi(10^6)
使用二重循环，对任何在范围内的素数对
计算其位组合的AND值
再计算位组合的1的数量
选择最少数量的1对应的素数对(X, Y)
则得到(2, 3, 5, X, Y)最佳组合
同样能得到类似的(2, 3, 7, X, Y)组合

mathe 发表于 2008-10-9 21:14:26

同我想到一起了。而且我觉得L5和L7都不会太大

medie2005 发表于 2008-10-9 21:20:24

L5和L7都在5000左右。

无心人 发表于 2008-10-9 21:52:10

:lol

我在尝试用haskell生成T5 T7
可惜不会处理文本文件
哈哈

在学呢

medie2005 发表于 2008-10-9 23:37:55

（2，3，5，102199，867857）      31 fail

无心人 发表于 2008-10-10 07:53:16

:)

你还在随机抽取？

按我说的算法
假设5000个候选
1秒至少可测试1万个
用C/C++还要多
那么测试10万素数底
只需要5万秒
而最后的两两求与
其工作量是
5000/128 <= 40
40 * (100000)^2 = 4000亿
大概2个小时能完成
搜索1的个数，似乎我们做过相关工作的
呵呵

mathe 发表于 2008-10-10 08:41:08

那个错误的结果已经从网页http://math.crg4.com/primes.html上去除了。
不知道medie2005是否愿意将自己的名字列在那个网页上（作为贡献者之一）；如果不愿意，让他使用medie2005如何？

无心人 发表于 2008-10-10 10:20:40

呵呵
media2005叫什么？

medie2005 发表于 2008-10-10 10:22:33

我叫吴新仁，跟你同名哦。:lol

无心人 发表于 2008-10-10 10:42:11

可是我真名叫
风烟语啊

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