无心人 发表于 2010-7-14 20:09:24

小素数测试专题

先发下，压缩的1950内的素数表3061772255,3589881307,3941801551,3869175206,1003737868,1789221341,2025689703,1448519198,3727535587,3646245930,60813475,788046164,1726563581,3090813942,1161440076,2354364177以30k + 1， 7， 11， 13， 17， 19， 23， 29为表示形式，每字节表示一组，每4字节组成一个32位双字，k = 1到64的全部结果压缩到16个双字

无心人 发表于 2010-7-14 21:25:47

32位的素性测试，应该是可以分成几种不同方法的
1、完全的试除
2、试除辅助Miller Rabin测试
3、完全的Miller Rabin测试

无心人 发表于 2010-7-14 21:58:55

打包素数的代码
let power2 = take 32 (iterate (*2) 1)
*Primes List> let pack32 = zip (sort , j <- [1, 7, 11,
13, 17, 19, 23, 29], let x = i + j]) power2
*Primes List> let pack32b b = sum \$ map (\(_, y) -> y) \$ filter (\(x, _) -> isPr
ime x) \$ map (\(x, y) -> (x + b, y)) pack32
*Primes List> let pack2p16 = , let x = pack32b (120 * i+ 30)]
结果

qianyb 发表于 2010-7-17 17:05:20

1# 无心人


这样分组,不是有些重复了吗,如77,91
可以把3*5*7*11*13*17*19*23*29=3234846615分成一组

〇〇 发表于 2010-7-17 20:22:20

用hash最快吧

无心人 发表于 2010-7-18 10:29:21

呵呵，有人关心了
这个东西最近有点不想做了
过几天做个测试集
至少10万数据，包括5%素数，全部spsp(2)，其他合数

无心人 发表于 2010-7-18 10:31:34

4#
老大你说的俺不懂，并不是最好的压缩形式，诸位有好方式，可以讨论

无心人 发表于 2010-7-18 10:38:03

做hash在2, 3, 5, 7那个帖子里，我测试了几个
单 hash并不很理想，要到20000以上的素数才保证不重复

我在考虑取中间9位的形式，看2次位组合是不是能保证足够覆盖

qianyb 发表于 2010-7-18 15:38:35

我还是不理解你的压缩方法，压缩了以后判断素数是怎么用的？

hujunhua 发表于 2010-7-18 19:25:48

我这瞎子都摸清大象了，qianyb还没搞懂？又想多了吧。
页: [1] 2
查看完整版本: 小素数测试专题