郭有没有兴趣做出一个确定性的素性检测函数

无心人

继续优化函数
*Primes List> let m1 p = map (\x -> m2 x 8 p) [1..p-1]
*Primes List> let m2 p = filter (\x -> not (any (==0) x)) (m1  p)

无心人

结论
7 = {2， 4， 5， 6}
11 = {1， 3， 10}
13 = {1， 2， 3， 7， 12}
即可，再大的素数候选就太多了

无心人

下面是100内素数p满足条件的模的可能个数
[(3,1),(5,1),(7,4),(11,3),(13,5),(17,9),(19,11),(23,15),(29,21),(31,26),(37,29),
(41,33),(43,35),(47,39),(53,45),(59,51),(61,53),(67,59),(71,63),(73,65),(79,71),
(83,75),(89,81),(97,89)]

gxqcn

对于搜索连续长度为10以上的素数，我们只需要搜索形式如2*3*5*11*k-1的素数。
而如果搜索长度为12以上的，只需要搜索形式如2*3*5*11*13*k-1的素数
mathe 发表于 2010-7-8 15:29

根据 36# mathe 的推导，27# 还可进一步加强为：

对于搜索连续长度为10以上的素数，我们只需要搜索形式如2^10*3*5*11*k-1的素数。
而如果搜索长度为12以上的，只需要搜索形式如2^12*3*5*11*13*k-1的素数

无心人

*Primes List> let is7 n = any (==(mod n 7)) [2,4,5,6]
*Primes List> let is11 n = any (==(mod n 11)) [1, 3, 10]
*Primes List> let is13 n = any (==(mod n 13)) [1, 2, 3, 7, 12]

mathe

根据  36# mathe  的推导，27# 还可进一步加强为：

gxqcn 发表于 2010-7-8 16:55

这个结论不成立

gxqcn

我是这样想的：
对于连续长度为10以上的素数，这个数必须为 2^10*t-1 型，又同时得为 2*3*5*11*k-1 型，此时必须 2^9|k，
所以才有上述加强的说法，不知哪里不对？

无心人

是不成立

mathe

$(2^10t-1)(Mod P)$未必是$2^10t-1$

无心人

放弃计算了，只能用C/C++了
haskell计算候选素数，就N慢了
不过，筛选的就已经很少了
大概2000左右才有一个