无心人 发表于 2010-7-8 16:05:59

肯定是10k - 1形式的

无心人 发表于 2010-7-8 16:08:42

你说的是30 k - 1
下面依次可以考虑7， 11， 13， 17， 19素数的模

mathe 发表于 2010-7-8 16:09:09

我的方法可以改善到30k-1
另外，我们还可以要求模7为{2,4,5,6}之一
同样还可以对模11进行处理，显然余数10是可以的，但是对于其他非0余数，我们还需要判断一下，有多少个8次以内不会到达0（只有两个），所以模11比模7更加高效

无心人 发表于 2010-7-8 16:09:24

8链起始素数很可能大于10^8的
我搜索不完全

mathe 发表于 2010-7-8 16:16:42

只需要搜索1/30,如果在使用模7和模11，大概可以接近到1/200，这个数据量应该是可以忍受的

无心人 发表于 2010-7-8 16:19:17

暴力搜索到2329469的，是没有8序列的

无心人 发表于 2010-7-8 16:28:45

7 = {2， 4， 5， 6}
11 = {1， 3， 10}
13 = {1， 2， 3， 7， 12}

无心人 发表于 2010-7-8 16:29:55

Haskell测试代码
let m2 n i p = take i (iterate (\x ->mod (x * 2 + 1) p) n)
*Primes List> map (\x -> m2 x 8 11)
[,,,,[5,0,1,
3,7,4,9,8],,,,[9,8,6,2,5,0,1,
3],]
*Primes List> map (\x -> m2 x 8 13)
[,,,,[
5,11,10,8,4,9,6,0],,,,[9,6
,0,1,3,7,2,5],,,]

无心人 发表于 2010-7-8 16:33:27

*Primes List> map (\x -> m2 x 8 17)
[,,,[4,9,2,5,11,6,13
,10],,,,[8,0,1,3,7,1
5,14,12],,,,[12,8,0,
1,3,7,15,14],,,,[16,
16,16,16,16,16,16,16]]
19的
[,,,[4,9,0,1,3,7,15,1
2],,,,[8,17,16,14,
10,2,5,11],,,,[12,6,13,
8,17,16,14,10],,,[15,12,6,13,8,17,16,1
4],,,]

无心人 发表于 2010-7-8 16:35:37

17 = {2， 4， 5， 6， 9， 10， 11， 13， 16}
19 = {1， 3， 6， 7， 8， 12， 13， 15， 16， 17， 18}！！！！！！！！！
页: 1 2 3 4 [5] 6 7 8
查看完整版本: 郭有没有兴趣做出一个确定性的素性检测函数