求10的10次方以内的素数，怎么能在几小时内算出来结果？

x2

原帖由 皇家救星 于 2009-4-22 20:12 发表
总觉概率算法得很诡异

如果我说一个数不能被1-100之间任何数整除，那这个数是还真的是素数呢，显然不是

但是这个数是合素的概率是多少呢？ (1/2)^100

如何证明你发明的这个算法,(1/2)^100的依据是什么

[ 本帖最后由 x2 于 2009-4-23 16:03 编辑 ]

皇家救星

这个不是一个算法，只是一个对概率算法的质疑。 -

--------------------------------

a除b的余数有两种，一种是0，另一种是非0

a除b后余数是0，则说明它不是素数，否则说明它有可能是素数

所以a除b后余数不为0，则其是素数的概率是1/2

接下来再算a%c，如果仍是非0，则其是素数概率是1/2*1/2

这样算下去，除100次自然是(1/2)^n

皇家救星

原帖由 zliming 于 2009-4-23 15:21 发表


B,只存储个位数是 1，3，7，9的整数
这个其实和去掉偶数的方法一样，前期干掉一堆数。比去偶数法再删一个 个位数为5的
去偶数后第二次筛可以全干掉个位为5的
剩下的是否 乘还是加法筛没有看出很大差别
...

lbab的算法能省下不少内存，可能与这个有关

arust

有一个叫做 HugeCalc 的国产软件，附带了一个计算素数的工具，计算速度极快，可惜作者没有公开算法

prolj

原帖由 arust 于 2009-4-23 18:56 发表
有一个叫做 HugeCalc 的国产软件，附带了一个计算素数的工具，计算速度极快，可惜作者没有公开算法

mik能反汇编，我还不熟

rainyday713

71,72楼的兄弟，建议你们看下《初等数论》里面Fermat小定理和平方剩余的相关内容。

Rabin-Miller素性检验算法，是经过严格证明的。

数学基础对于算法是很重要的，尤其是素性检验。

[ 本帖最后由 rainyday713 于 2009-4-23 21:44 编辑 ]

给个理由先

原帖由 arust 于 2009-4-23 18:56 发表
有一个叫做 HugeCalc 的国产软件，附带了一个计算素数的工具，计算速度极快，可惜作者没有公开算法

我试了下
0~2^32-1 之间的用了才 0.000005s

zliming

HugeCalc 不知道怎么用，输出结果看不明白。和windows7不兼容？

lbaby

原帖由 zliming 于 2009-4-23 15:21 发表


B,只存储个位数是 1，3，7，9的整数
这个其实和去掉偶数的方法一样，前期干掉一堆数。比去偶数法再删一个 个位数为5的
去偶数后第二次筛可以全干掉个位为5的
剩下的是否 乘还是加法筛没有看出很大差别
...

点击下边的链接：

http://www.esnips.com/doc/4358e4 ... 46-5f3adb160a31/tst



选 择

Download tst.rar

就可以下载代码了


说实话，代码我也看不懂了

blackuhlan

我一直想弄个大数是否质数的算法，但一直没有什么眉目，不知道兄弟们有什么好的思路。大数是指很大很大的数.