1. 素数的判定
方法1:1到蛮力测试
//素数的判定
//2 到sqrt(x) 整除x,只要有一个能除尽,说明x 不是素数
BOOL isPrime1(UINT32 x)
{
switch(x)
{
case 0:
return FALSE;
case 1:
return FALSE;
case 2:
return TRUE;
case 3:
return TRUE;
default:
break;
}
//以上是处理边界情况1 2 3
for(UINT32 i = 2; i <= static_cast<UINT32>(sqrt(static_cast<float>(x)));
++i)
{
if(0U == x % i)
{
return FALSE;
}
}
return TRUE;
}
方法2:用素数表测试
//素数的判定
//如果x 不是太大,素数表的最大素数是不小于sqrt(x)的最大素数,用素数表的每个素数
//去整除x,只要有一个能整除,说明x是合数,返回FALSE;
//只有小于sqrt(x)内的所有素数都不能整除x,说明x是素数,返回TRUE
UINT32 list[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,
83,89,97,101};//sqrt(10000)内的素数表
BOOL isPrime2(UINT32 x)
{
switch(x)
{
case 0:
return FALSE;
case 1:
return FALSE;
case 2:
return TRUE;
case 3:
return TRUE;
default:
break;
}
//以上是处理边界情况1 2 3
UINT32 i = 0;
while(list[i] * list[i] <= x)
{
if(0 == x % list[i])
{
return FALSE;
}
++i;
}
return TRUE;
}
方法3:米勒-拉宾测试
令大奇数n=m+1,其中l是非负整数,m是正奇数,若1()或-1(),,则称n通过b为基的米勒-拉宾测试。
定理 如果n是奇合数,0<b<n,则使n通过Miller-Rabin测试的b的个数不超过(n-1)(即n通过b的Miller-Rabin测试的概率最高是)。
例如随机选取n,通过依次随机取的Miller-Rabin测试,n是合数的概率不超过==0.00000095,至少以0.999999的概率判定n是素数。
定理简单明了,但证明却需要许多准备。
//米勒-拉宾测试
//n=2^m*l+1
BOOL passMillerRabinTest(UINT32 n)
{
UINT<chmetcnv unitname="l" sourcevalue="32" hasspace="True" negative="False" numbertype="1" tcsc="0">32 l</chmetcnv> = 0U;
UINT<chmetcnv unitname="m" sourcevalue="32" hasspace="True" negative="False" numbertype="1" tcsc="0">32 m</chmetcnv> = n - 1;
while(0U == m % 2U)
{
l += 1;
m /= 2U;
}
UINT32 b = rand() % (n - 1U) + 1;
if(1U == modExp(b, m, n))
{
return TRUE;
}
UINT32 j = m;
for(UINT32 i = 0U; i < l; ++i)
{
if(modExp(b, j, n) == n - 1)
{
return TRUE;
}
j *= 2;
}
return FALSE;
}
2. 产生一个素数
在实际应用中,经常需要大素数,产生大素数的过程如下:
(1)产生一个n位随机数p(n位二进制);
(2)将最高位和最低为置为1(最高位置1保证了产生的素数足够大,而最低位为1保证为奇数);
(3)检查p是否能被小素数整除:3,5,7,11等。许多实际应用中都用小于256的所有素数去除p;
(4)对于随机数a,进行Miller-Rabin测试,如果p通过了,则产生另一个随机数a再进行测试。选择值小一些的额a可以令计算更快。做5次测试,只要p没有通过其中的一次,转(1)重新开始;
另一种方法不是每次产生一个随机数,而是从一个起始数开始逐次递增,直到找到素数。
步骤(3)是可选的,但很有用。测试一个随机奇数p是否能被3,5,7整除,可以在第(4)步测试前去掉54%的基数,用100以内的素数测试可以去掉76%的奇数,而用256以内的素数测试可以去掉80%的奇数。一般地,奇数中不为任何小于n的素数的倍数的数的比例占1.12/lnn。
查看原文
分享到:
相关推荐
50000000(五千万)以内质数(素数)3001134(约三百万)个,普通pc演算(i7处理器)#质数#素数#合数
求解第N个质数(第N个素数)vs2010项目计算时间差不多 用的是试除法
//【程序2】 //题目:判断101-200之间有多少个素数,并输出所有素数。 //程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数), //如果能被整除, 则表明此数不是素数,反之是素数。
1亿以内的质数(共5761455个数).txt
自定义函数求素数(质数).py
Android项目源码,用于显示质数和素数的数学工具的手机APP
质数环是相邻两数相加之和为质数数字环。本程序实现的是1-20个数构成的质数环。每个数字只能使用一次,相邻两数相加之和为质数,首尾数字相加也为质数。
编制一个返回值为bool型的函数isPrimer(),用于判断参数是否为素数,调用函数回答以下问题(请包括在一个main()函数中完成,输出时,用明显的提示语,说明正在完成哪个任务。) (1)输出10000以内的所有素数。 (2...
两百万的素数/质数,最大素数/质数35499293,可用于与数论相关的计算。
素数(prime number)又称质数,有无限个。除了1和它本身外,不能被其他自然数整除。换句话说就是该数除了1和它本身以外不再有其他的因数的数。 注意:最小的素数是2。 话不多说,上代码! prime=[] #用一个列表来存储...
革命性素数算法:计算1亿内素数只要1.6秒 算法基本跟之前发的C#版相同(http://download.csdn.net/source/690005内有算法描述),由我的朋友杨力2年前设计,时间复杂O(n)。我对其进行了革命性的数据结构改进,空间...
14988613以内的素数(质数)表 代码见 http://blog.csdn.net/forandever/archive/2009/07/07/4327026.aspx
C语言,计算一个数是否素数(质数)的程序,
素数又叫质数,质数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。 问题: 输入一个整数n,输出1~n中的素数,里有详细解释,有问题也欢迎留言!谢谢支持啦~
跟我学Java面向对象程序设计技术及应用——识别某个自然数是否为质数(素数)的Java 程序实现示例 1 什么是质数(素数) 1 什么是质数(素数) 对于什么是质数(Prime Number),读者可以查询百科。在百科中的定义...
最快的素数筛法, 2秒初始化后在奔腾4上能算出2^31 以内素数个数,之后10ms内算出任意 0-2^31之间素数个数,可快速的计算第k个素数, 枚举区间[n, m](m - n ^5)以内素数等 还可以计算第k个数,分因素分解 Prime[78499]...
前100万个质数、素数 sqlserver2008 bak文件 ,倒入直接可用,可以自行导出sql文件 已经 牌号 顺序存放 ,并严格 核查
Android项目源码显示质数和素数的数学工具是一个数学工具项目源码,可以很方便的显示出固定范围的素数和质数之和或者质数的数量。是一个专业性比较强的项目。一般人用不到。
判断质数 素数——我知道的最快的方法.pdf
算法-求一亿以内的回文质数(素数).rar