标题:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
只看楼主
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
结帖率:100%
 问题点数:0 回复次数:400 
各位老师好!求助编辑一个大整数的快速乘除法可调用程序
我用于判断和筛选10亿内的素数表的程序速度太慢,1亿内的需要3个小时,10亿内的更是24个小时没有结果,只好关闭了,已经是采用了快速判断法,但效果低,原因是不会大整数的快速乘除法程序,希望老师帮助。我仅会一点VB语句,希望是用VB编程的。
我的判断素数的程序,对单个整数几十位的可以迅速判断,素数表就不行了,只能到1亿,单个整数100位以上的也不行。希望老师指点,会快速乘法除法的原理的也请指导帮助!
谢谢!
   祝愿各位老师,新年快乐,阖家幸福安康,万事如意!

[此贴子已经被作者于2020-2-10 23:14编辑过]

搜索更多相关主题的帖子: 乘除法 整数 快速 老师 判断 整数 判断 乘除法 快速 老师 
2020-02-10 23:10
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
得分:0 
你的程序是怎样的?大数乘除都可以百度到的,可作为参考。

[此贴子已经被作者于2020-2-10 23:29编辑过]

2020-02-10 23:25
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
谢谢老师!都是VC的没有VB的,看不懂!我的程序效率低,调试了多次结果是正确的,就是速度慢,而且最多也不知道算多少位,太长的就溢出吧,关键是速度慢!
2020-02-11 00:24
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
233333333333333333333333333333333333333333333333333333这是素数有54位

这个是用我的程序判断的,程序用了1分钟还是几分钟?估计的,没有计算时间的程序。
2020-02-11 00:27
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
得分:0 
10亿内素数用long型数据即可,不需要大数乘除法,用欧拉筛法应该10秒内可建立一个10亿内的素数表。

能编个毛线衣吗?
2020-02-11 09:42
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
不行,超过9位就溢出,不仅是素数表还计算下面的数据,这个数程序运行了至少半个小时:
1000620000与1000720000之间有287对孪生素数对:
1000620317和 1000620319  孪中1000620318
1000620347和 1000620349  孪中1000620348
1000621709和 1000621711  孪中1000621710
1000621799和 1000621801  孪中1000621800
1000622009和 1000622011  孪中1000622010
1000622087和 1000622089  孪中1000622088
1000622891和 1000622893  孪中1000622892
1000622921和 1000622923  孪中1000622922
1000622969和 1000622971  孪中1000622970
1000623341和 1000623343  孪中1000623342
1000623989和 1000623991  孪中1000623990
1000624307和 1000624309  孪中1000624308
1000624619和 1000624621  孪中1000624620
1000624991和 1000624993  孪中1000624992
1000625231和 1000625233  孪中1000625232
1000625411和 1000625413  孪中1000625412
1000625651和 1000625653  孪中1000625652
1000625699和 1000625701  孪中1000625700
1000626047和 1000626049  孪中1000626048
2020-02-11 10:09
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
long型的数据?可能是行,咱不会,仅会有限个vb语句,不精通。但是判断几十位几百位的整数是否是素数,必须用大整数的快速乘法除法程序,欢迎指导!
谢谢楼上的老师!
2020-02-11 10:15
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
得分:0 
long型数据可以做20亿内的整数计算,如果是几十上百位当然要使用大数乘除,而对大数的素数判断不能使用常规的算术运算,一般使用Miller-Rabin素性测试方法,有点复杂,其中要用到快速模运算和快速积运算。仅仅实现大数加减乘除很简单,但做素性测试还不够的。

能编个毛线衣吗?
2020-02-11 10:31
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
对,我的程序就是个太慢效率低。我的大数程序好像超过2万位就内存不足溢出了,不能算更大的,上万位的整数算一步乘法的时间也是长,太慢。
2020-02-11 11:25
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
判断大素数我采用的是RSA密码的逆命题,用到快速幂模算法,是确定性的算法,小于5位的就失效了,因为明文采用3位的,用一位的数字怕不准,明文是余数才能还原的,除数低于3位余数就不会是3位的,还原不回去原理就失效。大于5位的是成立的,由于我的大整数的乘除法速度太慢,所以几十位的运算结果消耗时间还是能忍受的,再大的就无法忍受了。原理上是可以的。
谢谢老师!欢迎指导!

[此贴子已经被作者于2020-2-11 11:47编辑过]

2020-02-11 11:34



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-499181-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.050456 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved