- 浏览: 485318 次
- 性别:
- 来自: 长沙
文章分类
最新评论
-
Source_野驴:
...
jsp静态化和伪静态化 -
zidanzzg:
很好的知识,找到了利用异或交换数值的理论支持,谢谢分享
XOR的性质和运算 -
ueseu:
引用(2) DomainDomain域名也是Cookie的一部 ...
Cookie的组成 -
ueseu:
引用Secure取true或者false值。如果为true,那 ...
Cookie的组成 -
liqi___123:
理解得很透彻,谢谢!!
ROLAP、MOLAP和HOLAP联机分析处理区别
浅析求素数算法
时间: 2006-10-27
注意: 如果没有特殊说明, 以下讨论的都是针对n为素数时的时间复杂度
1. 根据概念判断:
如果一个正整数只有两个因子, 1和p,则称p为素数.
bool isPrime(int n) { if(n < 2) return false; for(int i = 2; i < n; ++i) if(n%i == 0) return false; return true; }
时间复杂度O(n).
2. 改进, 去掉偶数的判断
bool isPrime(int n) { if(n < 2) return false; if(n == 2) return true; for(int i = 3; i < n; i += 2) if(n%i == 0) return false; return true; }
时间复杂度O(n/2), 速度提高一倍.
3. 进一步减少判断的范围
定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
证明: 如果n不是素数, 则由定义n有一个因子d满足1<d<n.
如果d大于sqrt(n), 则n/d是满足1<n/d<=sqrt(n)的一个因子.
bool isPrime(int n) { if(n < 2) return false; if(n == 2) return true; for(int i = 3; i*i <= n; i += 2) if(n%i == 0) return false; return true; }
时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).
4. 剔除因子中的重复判断.
例如: 11%3 != 0 可以确定 11%(3*i) != 0.
定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个"素数"因子d.
证明: I1. 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
I2. 如果d是素数, 则定理得证, 算法终止.
I3. 令n=d, 并转到步骤I1.
由于不可能无限分解n的因子, 因此上述证明的算法最终会停止.
// primes[i]是递增的素数序列: 2, 3, 5, 7, ... // 更准确地说primes[i]序列包含1->sqrt(n)范围内的所有素数 bool isPrime(int primes[], int n) { if(n < 2) return false; for(int i = 0; primes[i]*primes[i] <= n; ++i) if(n%primes[i] == 0) return false; return true; }
假设n范围内的素数个数为PI(n), 则时间复杂度O(PI(sqrt(n))).
函数PI(x)满足素数定理: ln(x)-3/2 < x/PI(x) < ln(x)-1/2, 当x >= 67时.
因此O(PI(sqrt(n)))可以表示为O(sqrt(x)/(ln(sqrt(x))-3/2)),
O(sqrt(x)/(ln(sqrt(x))-3/2))也是这个算法的空间复杂度.
5. 构造素数序列primes[i]: 2, 3, 5, 7, ...
由4的算法我们知道, 在素数序列已经被构造的情况下, 判断n是否为素数效率很高;
但是, 在构造素数序列本身的时候, 是否也可是达到最好的效率呢?
事实上这是可以的! -- 我们在构造的时候完全可以利用已经被构造的素数序列!
假设我们已经我素数序列: p1, p2, .. pn
现在要判断pn+1是否是素数, 则需要(1, sqrt(pn+1)]范围内的所有素数序列,
而这个素数序列显然已经作为p1, p2, .. pn的一个子集被包含了!
// 构造素数序列primes[] void makePrimes(int primes[], int num) { int i, j, cnt; primes[0] = 2; primes[1] = 3; for(i = 5, cnt = 2; cnt < num; i += 2) { int flag = true; for(j = 1; primes[j]*primes[j] <= i; ++j) { if(i%primes[j] == 0) { flag = false; break; } } if(flag) primes[cnt++] = i; } }
makePrimes的时间复杂度比较复杂, 而且它只有在初始化的时候才被调用一次.
在一定的应用范围内, 我们可以把近似认为makePrimes需要常数时间.
在后面的讨论中, 我们将探讨一种对计算机而言更好的makePrimes方法.
6. 更好地利用计算机资源...
当前的主流PC中, 一个整数的大小为2^32. 如果需要判断2^32大小的数是否为素数,
则可能需要测试[2, 2^16]范围内的所有素数(2^16 == sqrt(2^32)).
由4中提到的素数定理我们可以大概确定[2, 2^16]范围内的素数个数.
由于2^16/(ln(2^16)-1/2) = 6138, 2^16/(ln(2^16)-3/2) = 6834,
我们可以大概估计出[2, 2^16]范围内的素数个数6138 < PI(2^16) < 6834.
在对[2, 2^16]范围内的素数进行统计, 发现只有6542个素数:
p_6542: 65521, 65521^2 = 4293001441 < 2^32, (2^32 = 4294967296)
p_6543: 65537, 65537^2 = 4295098369 > 2^32, (2^32 = 4294967296)
在实际运算时unsigned long x = 4295098369;将发生溢出, 为131073.
在程序中, 我是采用double类型计算得到的结果.
分析到这里我们可以看到, 我们只需要缓冲6543个素数, 我们就可以采用4中的算法
高效率地判断[2, 2^32]如此庞大范围内的素数!
(原本的2^32大小的问题规模现在已经被减小到6543规模了!)
虽然用现在的计算机处理[2, 2^16]范围内的6542个素数已经没有一点问题,
虽然makePrimes只要被运行一次就可以, 但是我们还是考虑一下是否被改进的可能?!
我想学过java的人肯定想把makePrimes作为一个静态的初始化实现, 在C++中也可以
模拟java中静态的初始化的类似实现:
#define NELEMS(x) ((sizeof(x)) / (sizeof((x)[0])))
static int primes[6542+1];
static struct _Init { _Init(){makePrimes(primes, NELEMS(primes);} } _init;
如此, 就可以在程序启动的时候自动掉用makePrimes初始化素数序列.
但, 我现在的想法是: 为什么我们不能在编译的时候调用makePrimes函数呢?
完全可以!!! 代码如下:
// 这段代码可以由程序直接生成 const static int primes[] = { 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,103, 107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211, 223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331, 337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449, 457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587, 593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709, 719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853, 857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991, ... 65521, 65537 };
有点不可思议吧, 原本makePrimes需要花费的时间复杂度现在真的变成O(1)了!
(我觉得叫O(0)可能更合适!)
7. 二分法查找
现在我们缓存了前大约sqrt(2^32)/(ln(sqrt(2^32)-3/2))个素数列表, 在判断2^32级别的
素数时最多也只需要PI(sqrt(2^32))次判断(准确值是6543次), 但是否还有其他的方式判断呢?
当素数比较小的时候(不大于2^16), 是否可以直接从缓存的素数列表中直接查询得到呢?
答案是肯定的! 由于primes是一个有序的数列, 因此我们当素数小于2^16时, 我们可以直接
采用二分法从primes中查询得到(如果查询失败则不是素数).
// 缺少的代码请参考前边 #include <stdlib.h> static bool cmp(const int *p, const int *q) { return (*p) - (*q); } bool isPrime(int n) { if(n < 2) return false; if(n == 2) return true; if(n%2 == 0) return false; if(n >= 67 && n <= primes[NELEMS(primes)-1]) { return NULL != bsearch(&n, primes, NELEMS(primes), sizeof(n), cmp); } else { for(int i = 1; primes[i]*primes[i] <= n; ++i) if(n%primes[i] == 0) return false; return true; } }
时间复杂度:
if(n <= primes[NELEMS(primes)-1] && n >= 67): O(log2(NELEMS(primes))) < 13;
if(n > primes[NELEMS(primes)-1]): O(PI(sqrt(n))) <= NELEMS(primes).
8. 素数定理+2分法查找
在7中, 我们对小等于primes[NELEMS(primes)-1]的数采用2分法查找进行判断.
我们之前针对2^32缓冲的6453个素数需要判断的次数为13次(log2(1024*8) == 13).
对于小的素数而言(其实就是2^16范围只内的数), 13次的比较已经完全可以接受了.
不过根据素数定理: ln(x)-3/2 < x/PI(x) < ln(x)-1/2, 当x >= 67时, 我们依然
可以进一步缩小小于2^32情况的查找范围(现在是0到NELEMS(primes)-1范围查找).
我们需要解决问题是(n <= primes[NELEMS(primes)-1):
如果n为素数, 那么它在素数序列可能出现的范围在哪?
---- (n/(ln(n)-1/2), n/(ln(n)-3/2)), 即素数定理!
上面的代码修改如下:
bool isPrime(int n) { if(n < 2) return false; if(n == 2) return true; if(n%2 == 0) return false; int hi = (int)ceil(n/(ln(n)-3/2)); if(n >= 67 && hi < NELEMS(primes)) { int lo = (int)floor(n/(ln(n)-1/2)); return NULL != bsearch(&n, primes+lo, hi-lo, sizeof(n), cmp); } else { for(int i = 1; primes[i]*primes[i] <= n; ++i) if(n%primes[i] == 0) return false; return true; } }
时间复杂度:
if(n <= primes[NELEMS(primes)-1] && n >= 67): O(log2(hi-lo))) < ???;
if(n > primes[NELEMS(primes)-1]): O(PI(sqrt(n))) <= NELEMS(primes).
9. 打包成素数库(给出全部的代码)
到目前为止, 我已经给出了我所知道所有改进的方法(如果有人有更好的算法感谢告诉我).
这里需要强调的一点是, 这里讨论的素数求法是针对0-2^32范围的数而言, 至于像寻找
成百上千位大小的数不在此讨论范围, 那应该算是纯数学的内容了.
代码保存在2个文件: prime.h, prime.cpp.
// file: prime.h #ifndef PRIME_H_2006_10_27_ #define PRIME_H_2006_10_27_ extern int Prime_max(void); // 素数序列的大小 extern int Prime_get (int i); // 返回第i个素数, 0 <= i < Prime_max extern bool Prime_test(int n); // 测试是否是素数, 1 <= n < INT_MAX #endif /////////////////////////////////////////////////////// // file: prime.cpp #include <assert.h> #include <limits.h> #include <math.h> #include <stdlib.h> #include "prime.h" // 计算数组的元素个数 #define NELEMS(x) ((sizeof(x)) / (sizeof((x)[0]))) // 素数序列, 至少保存前6543个素数! static const int primes[] = { 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,103, 107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211, 223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331, 337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449, 457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587, 593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709, 719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853, 857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991, ... 65521, 65537 }; // bsearch的比较函数 static int cmp(const void *p, const void *q) { return (*(int*)p) - (*(int*)q); } // 缓冲的素数个数 int Prime_max() { return NELEMS(primes); } // 返回第i个素数 int Prime_get(int i) { assert(i >= 0 && i < NELEMS(primes)); return primes[i]; } // 测试n是否是素数 bool Prime_test(int n) { assert(n > 0); if(n < 2) return false; if(n == 2) return true; if(!(n&1)) return false; // 如果n为素数, 则在序列hi位置之前 int lo, hi = (int)ceil(n/(log(n)-3/2.0)); if(hi < NELEMS(primes)) { // 确定2分法查找的范围 // 只有n >= 67是才满足素数定理 if(n >= 67) lo = (int)floor(n/(log(n)-1/2.0)); else { lo = 0; hi = 19; } // 查找成功则为素数 return NULL != bsearch(&n, primes+lo, hi-lo, sizeof(n), cmp); } else { // 不在保存的素数序列范围之内的情况 for(int i = 1; primes[i]*primes[i] <= n; ++i) if(n%primes[i] == 0) return false; return true; } }
10. 回顾, 以及推广
到这里, 关于素数的讨论基本告一段落. 回顾我们之前的求解过程, 我们会发现
如果缺少数学的基本知识会很难设计好的算法; 但是如果一味地只考虑数学原理,
而忽律了计算机的本质特征, 也会有同样的问题.
一个很常见的例子就是求Fibonacci数列. 当然方法很多, 但是在目前的计算机中
都没有实现的必要!
因为Fibonacci数列本身是指数增长的, 32位的有符号整数所能表示的位置只有前46个:
static const int Fibonacci[] = { 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597, 2584,4181,6765,10946,17711,28657,46368,75025,121393,196418, 317811,514229,832040,1346269,2178309,3524578,5702887,9227465, 14930352,24157817,39088169,63245986,102334155,165580141,267914296, 433494437,701408733,1134903170,1836311903,-1323752223 };
因此, 我只需要把前46个Fibonacci数保存到数组中就可以搞定了!
比如: F(int i) = {return Fibonacci[i];} 非常简单, 效率也非常好.
同样的例子如求阶乘n!, 虽然也有很多数学上的描述, 但是计算机一般都表示不了,
我们直接把能用的计算好放到内存中就可以了.
总之, 许多东西本身是好的, 但是不要被它束缚了!
(完)
发表评论
-
模拟退火算法介绍
2013-05-30 11:53 1724模拟退火算法来源于固体退火原理,将固体加温至充分 ... -
大白话解析模拟退火算法
2013-01-25 06:01 903优化算法入门系列文章目录(更新中): 1. 模拟退火算 ... -
五个免费开源的数据挖掘软件
2013-01-22 12:56 1399Orange Orange 是一个基于组件的数 ... -
SPSS 19.01多国语言版破解版(包括简体中文)
2012-08-13 13:43 3049源地址:http://hi.baidu.com/kingz ... -
失血模型-贫血模型-充血模型-胀血模型
2012-07-20 13:21 2089一、失血模型 失血模型简单来说,就是domain ob ... -
NTFS的忠实秘书—USN日志
2012-07-20 11:24 1586最近,在江湖中出现了一匹黑马,名为Everything,用它 ... -
UltraEdit 与Unix 正则表达式
2011-11-18 14:21 1086UltraEdit 允许在搜索菜单 ... -
CPU设计原理
2011-08-09 14:30 2821序言 也许很多 ... -
XOR的性质和运算
2011-07-10 02:06 9078异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示, ... -
贫血/充血模型的解释以及一些经验
2011-06-18 13:33 1198为了补大家的遗憾,在此总结下ROBBIN的领域模型的一些观点和 ... -
PowerDesigner + 反向工程 + 数据字典
2011-05-12 10:58 1939操作步骤: 1. 打开 PowerDesinger ... -
软件开发和设计中的30条建议
2011-03-12 19:31 7621) 类名首字母应该大写。字段、方法以及对象(句柄)的首字母应 ... -
oschina技术实现
2011-03-10 14:15 1311简单说说 OsChina 的技术架构 OSChin ... -
编码字符集和字符集编码
2011-02-26 17:18 1092ASCII及相关标准 ... -
布隆过滤器(Bloom Filter)
2011-01-07 13:58 964在日常生活中,包括在 ... -
海明码的初识
2010-10-20 10:53 5536海明码是一位纠错码,即如果数据在传输过程中有一位出错 ... -
素数测试算法(基于Miller-Rabin的MC算法)
2010-10-19 15:26 3283在以往判断一个数n是 ... -
常用正则表达式[收藏]
2010-05-20 15:16 828"^\d+$" //非负整数(正整数 + ... -
RBAC基于角色的访问控制
2010-03-29 22:26 1275基于角色的访问 ... -
java各种模式的有趣见解
2010-03-09 15:46 6671、FACTORY—追MM少不了请 ...
相关推荐
最快求素数的算法,求100000000以下所有素数0.3秒 , 在10000000以下的数中找到664579个素数,耗时53毫秒
完整的 python 求素数算法 可以限定运行次数 可以中断保存
革命性素数算法:计算1亿内素数只要1.6秒 算法基本跟之前发的C#版相同(http://download.csdn.net/source/690005内有算法描述),由我的朋友杨力2年前设计,时间复杂O(n)。我对其进行了革命性的数据结构改进,空间...
大范围的素数算法,解决素数算法的问题,当程序需要,为什么非得20个字的描述呢
本篇文章将深入探讨几种经典的素数检测算法,这些算法适用于计算机编程,特别是对于参与ACM竞赛的学生来说,理解并掌握它们是十分有益的。 1. **基础判断法**: 最基础的素数检测方法是遍历从2到n-1的所有整数,...
### Java求素数的经典算法 #### 一、引言 素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的数。求解素数是计算机科学中的一个经典问题,特别是在密码学等领域有着重要的应用价值。Java作为一门流行...
在提供的压缩包中,有两个文件:`用开根号求素数.cpp`是源代码文件,包含了上述算法的实现;`用开根号求素数.exe`是编译后的可执行文件,可以直接在支持C++的环境中运行,无需再次编译。 通过这种方式,初学者不仅...
根据提供的文件内容,我们可以归纳出以下几个关键的知识点: ...以上内容综合了基础素数生成算法、命令行脚本实现、以及概率性素数测试算法的关键知识,希望能帮助理解素数算法的核心原理及其实际应用。
大素数的生成算法通常用于建立加密系统,如RSA公钥加密算法,其中需要找到两个非常大的质数来生成密钥对。速度很快的大素数生成算法对于提高系统的效率至关重要。 1. **大素数生成算法**: - **米勒-拉宾素性检验...
新手我热爱算法,第一次由个人琢磨出来的优化求任意两个数之间的素数算法,谢谢。我个人觉得,他似乎可以减少时间复杂度
很简单的 精炼的算法 代码很短 容易理解
在VB(Visual Basic)编程语言中,实现求素数的算法是一项基础且重要的任务。素数是指大于1的自然数,除了1和它自身以外,不能被其他自然数整除的数。例如,2、3、5、7、11等都是素数。下面我们将详细探讨如何使用VB...
### 相邻素数算法详解 #### 一、引言 在算法设计与分析的课程中,有一种较为重要的算法——相邻素数算法。本篇文章将详细介绍该算法的基本概念、实现原理以及具体的步骤演示,帮助读者深入理解并掌握这一算法。 #...
### Java中的素数算法 #### 一、引言 在计算机科学领域,特别是算法与数据结构的研究中,素数检测是一项基本且重要的任务。本文将详细介绍一个简单的Java程序,该程序能够有效地找出并打印出前500个素数。 #### ...
5. **[原创]浅析求素数算法 - LinuxSir_Org.mht**:素数检测是数论中的基础问题,也是构建其他复杂算法的基础,如素数筛法、Miller-Rabin测试等。此文档可能介绍了不同的求素数算法及其优缺点。 6. **大整数四则...
本项目"求某个正整数的素数算法应用程序"是利用C#的窗体应用(WinForms)来实现一个功能,即用户可以输入一个正整数,然后程序会计算并显示这个正整数有多少个素数因子。 素数是大于1且只有1和其本身两个正因子的...
求素数的算法通常采用试除法。首先,我们需要排除小于2的数,因为2是最小的素数。然后,我们从2开始,依次检查到这个数的平方根,看是否能整除这个数。如果在这一范围内找到了任何因子,那么这个数就不是素数;反之...
求200以内的所有素数的简单算法!很实用的求素数算法!
素数的求解算法主要包括素数检测算法和生成素数列表的方法。 1. **基本素性测试算法**: - 最简单的方法是从2到\( \sqrt{n} \)依次检查每个数是否能整除\( n \)。 - 代码示例(C语言): ```c bool IsPrime...