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

无心人

肯定是10k - 1形式的

无心人

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

mathe

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

无心人

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

mathe

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

无心人

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

无心人

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

无心人

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

无心人

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

无心人

17 = {2， 4， 5， 6， 9， 10， 11， 13， 16}
19 = {1， 3， 6， 7， 8， 12， 13， 15， 16， 17， 18}！！！！！！！！！