找回密码
 欢迎注册
查看: 8153|回复: 18

[求助] 一个素数判断程序问题,求助

[复制链接]
发表于 2009-2-9 16:38:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
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就会溢出,请教一下应该如何修改才可以支持更大的数字?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-9 17:01:32 | 显示全部楼层
居然用威尔逊定理,很低效的。
楼主看来还是个初学者,居然敢用浮点来进行数论计算。

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

点评

nyy
威尔逊定理连试除法都不如!  发表于 2023-5-12 09:16
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-9 18:02:39 | 显示全部楼层
我知道这个方法很低效,甚至没有什么用,但是这是一个确定性的判断方法,看看有没有可以优化的地方?
对于计算机计算,我的确是个初学者,希望多多指教了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-9 19:14:04 | 显示全部楼层
关键是, 目前来说
即使是尝试所有的$sqrt{n}$内的素数也比这个复杂度低

况且有至少两个实用性的确定性素性判定算法呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-9 19:29:15 | 显示全部楼层
这个算法的优化限度很大,我们可以很简单把计算量降低到原来的1/3甚至更低
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-9 20:03:31 | 显示全部楼层
假设你求一个100位的数字的素性

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

普通的PC这个数量级的整数大概在分钟单位的时间上能证明素性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-13 21:32:30 | 显示全部楼层

回复 1# 282842712474 的帖子

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


(当且仅当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/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-14 08:14:35 | 显示全部楼层
呵呵

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

椭圆曲线的有一个算法是5次多项式的确定性算法吧?
(不确定是5还是6了,要回家看书)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-12 09:15:21 | 显示全部楼层
gxqcn 发表于 2009-2-9 17:01
居然用威尔逊定理,很低效的。
楼主看来还是个初学者,居然敢用浮点来进行数论计算。

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

点评

别瞎说,我从来就没用这个定理去判别素数。  发表于 2023-5-12 09:43
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-5-12 09:49:32 | 显示全部楼层
nyy 发表于 2023-5-12 09:15
老鸟也是从菜鸟逐步成长的,当年你不也是起初用费马小定理判别素数吗????????

gxqcn,你不要再抵赖了,你当年就是用费马小定理来判定素数的,
后来在我的建议下,你才改成miller rabin,后来又改成BPSW算法的。
你不要认为我忘记了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 23:01 , Processed in 0.052782 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表