一款可瞬间判定素数的神奇小软件

moranhuishou

下面引用由天山草在 2008/09/30 09:27am 发表的内容：
楼主：
大数判素问题：在速度方面，您可以与美国的 Mathematica 软件进行比较；
国内的软件，可以与郭先强的大数计算器软件 HugeCalc 的速度进行比较。
不过，即使你的速度较慢，也不一定说明你的方法不行，因为 ...

Mathematica没用过，据说判素速度很快，但不知快到什么程度？例如一个小时能有多少位？能否判定3000位以上的？
郭先强的 HugeCalc 我试过，确实很快，很佩服。
但没有见过他的判素的软件。
[另外，郭先生好像对我有点小成见 ——“背地里”说我“坏话”.——随便说说，绝不会介意的。]

denglongshan

下面引用由moranhuishou在 2008/09/30 00:03am 发表的内容：
真的很抱歉，所以暂时不愿意公开，是因为——
1、如果没有价值（不是太快），则贻笑大方。
2、如果真的很快很有价值，公开了就都都会了，也就等于都不会，还是没有意义。
重要的是数学界没有人对真正有价值的成　...

公开才能证明你是首创，而且按照《知识产权法》，完成的那一时刻，就拥有产权。

moranhuishou

下面引用由denglongshan在 2008/09/30 11:38am 发表的内容：
公开才能证明你是首创，而且按照《知识产权法》，完成的那一时刻，就拥有产权。

等完成程序设计之后再谈“公开”问题，现为时尚早。不急。

moranhuishou

下面引用由moranhuishou在 2008/09/30 11:50am 发表的内容：
等完成程序设计之后再谈“公开”问题，现为时尚早。不急。

对于大数编程的程序安排问题，忽有新悟，惜不在家，手提没装程序，不能测试.过两天吧。
                                                   -------国庆日记

chinaunix

居然能够拿一般的计算机(32位)做到1秒种判断万位数字是否质数，我很想知道楼主的算法。

moranhuishou

下面引用由chinaunix在 2008/10/02 00:23am 发表的内容：
居然能够拿一般的计算机(32位)做到1秒种判断万位数字是否质数，我很想知道楼主的算法。

别听lz吹牛：现在只能用程序判定300亿以下的，判定几百位的还只能靠手工能计算，所以只能算是纸上谈兵，因为他编程的水平实在太烂。
不过不排除在最近真的能弄出来：）

moranhuishou

关于素数判定的程序，这一段没有解决。那位朋友能帮忙完成这一段大数乘除运算程序。其中a是小数，可以不考虑大数运算。
y = c
For i = 1 To n: a = Val(Mid$(b, i, 1))

y = ((1 + a) * y * y) / X

Next i
text1.text=y

njzzyy

下面引用由天山草在 2008/08/10 11:14pm 发表的内容：
请楼主算算，除了 11 这个数外，全由“1”组成的“1111……”形式的数，最小的素数是几个“1”组成的？-=-=-=-=- 以下内容由 天山草 在  时添加 -=-=-=-=-
回复楼下的：
您算得完全正确。只是不知今天为什么不能 ...

在<概率素数论>的"4. 2.2  重一素数个数"一节有这个问题的答案及数据,你可能快能看见了

wsc810

本人可以给出计算 a^((p-1)/2)mod p 的简洁算法 ，即费马方法 判断一个数是否为素数的 依据
首先 将(p-1)/2 分解为二进制数 ,其系数 计为   (由高到低)  b_n,b_（n-1）,b_(n-2),...b2,b1,b0.
然后计算 a^2=a1(mod p)  a2^2=a2(mod p)  a2^2=a3(mod p)
...a_(n-1)^2=a_n (mod  p)
再计算 (b0*a)*(b1*a1)*(b2*a2)*...*(b_n*a_n) =m (mod p).m 即为 所求的值
下面给出例子
  计算 2^54(mod 109)
2^2=4^2=16^2=38^2=27^2=75  (mod 109)(这里我连写了 ，,实际等号并不存在 ，实为 2^2=4 ,4^2=16,16^2=38 (mod 109)...)
      4*16*27*75=129600=108 （mod 109)
该算法的 最坏时间复杂度为 nlog(2)N ,这里，2为底数




[br][br]-=-=-=-=- 以下内容由 wsc810 在 时添加 -=-=-=-=-
[br][br]-=-=-=-=- 以下内容由 wsc810 在 时添加 -=-=-=-=-
不好意思我写错了 ，最坏时间复杂度为 2*log(2)N

moranhuishou

这里需要的是超大整数的程序运算代码。