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

282842712474

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就会溢出，请教一下应该如何修改才可以支持更大的数字？

gxqcn

居然用威尔逊定理，很低效的。 楼主看来还是个初学者，居然敢用浮点来进行数论计算。 建议将数据类型 Double 改成 Decimal 试试吧。

282842712474

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

无心人

关键是， 目前来说 即使是尝试所有的$sqrt{n}$内的素数也比这个复杂度低 况且有至少两个实用性的确定性素性判定算法呢

282842712474

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

无心人

假设你求一个100位的数字的素性 你的算法能在宇宙灭绝的时候结束么？ 普通的PC这个数量级的整数大概在分钟单位的时间上能证明素性

wayne

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

无心人

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

nyy

gxqcn 发表于 2009-2-9 17:01
居然用威尔逊定理，很低效的。
楼主看来还是个初学者，居然敢用浮点来进行数论计算。

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

nyy

nyy 发表于 2023-5-12 09:15
老鸟也是从菜鸟逐步成长的，当年你不也是起初用费马小定理判别素数吗？？？？？？？？

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