整数范围内的素数表

2022-03-11 22:40栏目:编程
TAG:

整数范围内的素数表

经过一个月的运算(不是我算的,是电脑算的),终于得到整数范围(4字节)内的所有素数表。

其中,短素数.dat 文件保存的是短整数范围(2字节)内的所有素数,一共3512个素数,最小素数为2,最大素数为32749。数据文件不含任何文件头和文件附加尾,直接就是所有数据,C语言可以用short int数据类型读取,Pascal可以用integer数据类型读取,易语言用短整数数据类型读取,每两个字节保存一个数。

整素数.dat 文件保存的是整数范围(4字节)内的所有素数,文件大小为406M,一共个,最小素数为32771,最大素数为。数据文件不含文件头和附加尾,直接就是所有数据,C语言可以用long数据类型读取,易语言用整数数据类型读取。

由于易语言的数据结构没有无符号整数,所以最大素数只能算到21亿,将程序移植到C,则可以使用无符号整数,可以使素数库增加到42亿。

判断N是否素数的基本算法:




素数表的应用。(程序说明)

为了加快程序运行速度,在程序加载时就将所有短素数放入内存,将整素数分成11组,每组个整数,需要时一次读入一组放入内存。

一、显示素数列表

每一页显示200个素数,从小到大,其中短素数在第1~17页,以及18页一部分。

二、快速验证素数

1、通过检索“短素数.dat”和“整素数.dat”来判定是否素数。速度非常快,但最大能判定的数大约为21亿,再大就无能为力了。

2、大数判定。通过逐个与素数库中素数求余来判定,当数字比较小时,速度略慢于方法1,但当数字非常大时,它可以利用素数库中已知结果进行验证。如此,当结果太大而实在不能判定时,意味着这个数不能被21亿以内的素数整除,因此,这个数是素数的概率非常大。

三、快速分解质因数

分解质因数。同上,如果非常大的数且精心选择,能够让程序无法分解,一般都可以分解。

四、求欧拉函数

欧拉函数是指所有小于n且与n互质的数的个数,我们通过求因子的方法来计算。求出n的所有素因子

,再用公式

计算。

五、解丢番图方程


因此,每一次迭代必然能使方程的系数变小,最终必然变成

或者

,直接求出。

六、RSA密码演示

本程序演示了常见的密码系统运作过程。注意,由于这个程序只是演示程序,所以它一次能加密的数字,限制在n以内。对于超过n的数字,请分段加密。本程序也不能直接加密文本,请勿尝试,会出不可预测的错误。

先在加密的原文框内输入原始数字,程序会输出一个标志数;将计算结果手动输入到解密程序的密文框,就可以得到原文。一般情况下都是可以正确计算,偶尔会出现错误。

特别说明:

不知道为什么,从易语言开发完成到现在,易语言和360就已知过不去。只要是易语言开发的程序,编译成exe文件后,必被360报毒,哪怕这个程序一句代码都没有也是木马,什么形式的木马不一定。

我也很苦恼,但是一点办法都没有。

我猜测是因为易语言使用全汉语编程,因此变量命名、函数命名和其他语言如C有所不同,也就被当成木马杀掉了。

出现这个问题的解决办法也很简单。请打开你的360杀毒软件。

这里有一个“查看隔离文件”,点击进入。


找到被隔离的程序“素数应用.exe”,并恢复就可以了。

本文来自网络,不代表山斋月平台立场,转载请注明出处: https://www.shanzhaiyue.top