一个素数判断程序问题，求助

cfan2021

Private Sub Form_Click()
Dim a As Double
Dim c As Double
Dim d As Double
Dim b As Double
a = InputBox("", "")
b = 1
c = 1

While b < a
c = c * b
b = b + 1
c = c Mod a
Wend

d = c + 1

If (d Mod a) = 0 Then Print "素数"
Print "不是素数"
End Sub

这是我的代码，理论上假如输入2300122，在运算过程中最大也不会出现14位数。可是我在调试的时候总是说我输入2300122就会溢出，请教一下应该如何修改才可以支持更大的数字？

ucobiit

居然用威尔逊定理，很低效的。
楼主看来还是个初学者，居然敢用浮点来进行数论计算。

建议将数据类型 Double 改成 Decimal 试试吧。

ameahopiyoyif

我知道这个方法很低效，甚至没有什么用，但是这是一个确定性的判断方法，看看有没有可以优化的地方？
对于计算机计算，我的确是个初学者，希望多多指教了

uzmetub

关键是， 目前来说
即使是尝试所有的$sqrt{n}$内的素数也比这个复杂度低

况且有至少两个实用性的确定性素性判定算法呢

akomosuse

这个算法的优化限度很大，我们可以很简单把计算量降低到原来的1/3甚至更低

aecupeemow

假设你求一个100位的数字的素性

你的算法能在宇宙灭绝的时候结束么？

普通的PC这个数量级的整数大概在分钟单位的时间上能证明素性

ogemama

印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳找到了一种极其简单的素数判定新方法（计算时间为多项式）：


（当且仅当n为素数时，最终输出数才为素数）
lnput： integer n>1
1.if (n is of the form a^b, b>1)output COMPOSITE;
2.R=2
3.while (r〈 n) ｛
4. if(ged(n,r)≠1) output COMPOSITE;
5. if(r is prime)
6. let q be the largest prime factor of r-1
7. if(q≥4^r/2 logn)and (n(r-1)/q≠1(mod r))
8. break;
9. r←r+1;
10. ｝
11.for a=1 to 2r^1/2 logn
12. if ((x-a)^n≠(x^n-a)(mod x^r-1,n))output COMPOSITE;
13.output PRIME;

see this :http://mathworld.wolfram.com/news/2002-08-07/primetest/

inabilezami

呵呵

楼上的算法虽然是多项式的
但比椭圆曲线的要慢

椭圆曲线的有一个算法是5次多项式的确定性算法吧？
（不确定是5还是6了，要回家看书）

ogemama

老鸟也是从菜鸟逐步长大的，当年你不也是起初用费马小定理判别素数吗？？？？？？？？

eheotolee

gxqcn，你不要再抵赖了，你当年就是用费马小定理来判定素数的，
后来在我的建议下，你才改成miller rabin，后来又改成BPSW算法的。
你不要认为我忘记了！