5818人阅读
1、任何一个合数（都指正整数，下同），都是几个质数的乘积。例如：18 = 2 * 3 * 3
2、如果一个数N不能整除M，则N也不能整除M*i，i=1, 2, 3....。即，N%M != 0，则 N%(M*i) &!= 0。例如，N不能整除2，那么N也不能整除6。因为，如果N能整除6，即，N%6 = 0，也就是 N%(2*3) = 0，也就是N能整除2，与前面矛盾。
3、如果N不是质数，那么N有满足1&d&=sqrt(N)（N的平方根）的一个质数因子 d 存在。因为如果N不是质数，根据条例1，N肯定可以分解为一堆质数的和，即肯定存在一个质数因子。如果找不到，那就说明N是质数，只能被1和自己本身整除。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A、依照判断素数的概念，我们可以从2~N-1，依次去除，看余数是否为0，复杂度为O(N)
B、改进一下，先判断 N%2 是否为0，如果不为0，即 N%(2*i) ！= 0（前面的条例2），所以只要再判断 3~N-1 之间的奇数即可，复杂度减半！为O(N/2)
同理，可以再判断 N%3 是否为0，如果不为0，则可以去掉后面的 3*i
C、其实，并不需要一直整除到N-1，而只要整除到 sqrt(N) 即可。如果 a & sqrt(N)， b&sqrt(N)，那么 a * b & sqrt(N)*sqrt(N) = N。如果b = N/a，那么b肯定是&=sqrt(N)。所以，只要判断小于等于sqrt(N)的数即可，再判断大于sqrt(N)的数就是在浪费时间了。
D、结合前面的 B 和 C，我们就可以先判断 N%2 是否为0，然后再判断 3~sqrt(N) 之间的奇数即可，复杂度为O(sqrt(N)/2)
E、根据条例3，如果N是质数，则N只能被1和N整除，如果N不是质数，那一定存在1&d&=sqrt(N)的一个质数因子。那么我们就可以取 2~sqrt(N) 之间的所有质数d，依次判断N%d 是否为0。如果判断均不等于0，就说明不存在这样的一个质数，也就是说N只能被1和本身整除，即N是质数。
详细的代码及深入阅读请参考：
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
注意: 如果没有特殊说明, 以下讨论的都是针对n为素数时的时间复杂度
1. 根据概念判断:
如果一个正整数只有两个因子, 1和p，则称p为素数.
bool isPrime(int n)
for(int i = 2; i & ++i)
if(n%i == 0)
时间复杂度O(n).
2. 改进, 去掉偶数的判断
bool isPrime(int n)
if(n == 2)
for(int i = 3; i & i += 2)
if(n%i == 0)
时间复杂度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)
for(int i = 3; i*i &= i += 2)
if(n%i == 0)
时间复杂度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)
for(int i = 0; primes[i]*primes[i] &= ++i)
if(n%primes[i] == 0)
假设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)
primes[0] = 2;
primes[1] = 3;
for(i = 5, cnt = 2; cnt & i += 2)
int flag =
for(j = 1; primes[j]*primes[j] &= ++j)
if(i%primes[j] == 0)
if(flag) primes[cnt++] =
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_, 65521^2 =
& 2^32, (2^32 = )
p_, 65537^2 =
& 2^32, (2^32 = )
在实际运算时unsigned long x = ;将发生溢出, 为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[];
static struct _Init { _Init(){makePrimes(primes, NELEMS(primes);} } _
如此, 就可以在程序启动的时候自动掉用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,
有点不可思议吧:), 原本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 int cmp(const int *p, const int *q)
return (*p) - (*q);
bool isPrime(int n)
if(n == 2)
if(n%2 == 0)
if(n &= 67 && n &= primes[NELEMS(primes)-1])
return NULL !=
bsearch(&n, primes, NELEMS(primes), sizeof(n), cmp);
for(int i = 1; primes[i]*primes[i] &= ++i)
if(n%primes[i] == 0)
时间复杂度:
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分法查找
在9中, 我们对小等于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)
if(n%2 == 0)
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);
for(int i = 1; primes[i]*primes[i] &= ++i)
if(n%primes[i] == 0)
时间复杂度:
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__
#define PRIME_H__
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
///////////////////////////////////////////////////////
// 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个素数!
// 我个人习惯缓冲前（1024*8）个:-)
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,
// 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)
if(!(n&1))
// 如果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);
// 不在保存的素数序列范围之内的情况
for(int i = 1; primes[i]*primes[i] &= ++i)
if(n%primes[i] == 0)
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,
65,,,,196418,
69,914296,
// 注意：数列到F47已经发生溢出！！！
因此, 我只需要把前46个Fibonacci数保存到数组中就可以搞定了!比如: F(int i){return Fibonacci(i);}非常简单, 效率也非常好.同样的例子如求阶乘n!, 虽然也有很多数学上的描述, 但是计算机一般都表示不了,我们直接把能用的计算好放到内存中就可以了.
总之, 许多东西本身是好的, 但是不要被它束缚了!
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：149444次
积分：2389
积分：2389
排名：第14319名
原创：102篇
评论：19条当前位置：
＞＞＞三个质数之和是86，那么这三个质数是______．-数学-魔方格
三个质数之和是86，那么这三个质数是______．
题型：填空题难度：偏易来源：不详
若三个质数都是奇数，则它们的和是奇数，则不等于86，所以三个数中必有一个偶数，偶数中只有2是质数，所以86-2=84，84=5+79=11+73=13+71=17+67=23+61=31+53=37+47=41+43，所以这三个质数是：（2，5，79）、（2，11，73）、（2，13，71）、（2，17，67）、（2，23，61）、（2，31，53）、（2，37，47）、（2，41，43）．故答案为：（2，5，79）、（2，11，73）、（2，13，71）、（2，17，67）、（2，23，61）、（2，31，53）、（2，37，47）、（2，41，43）．
马上分享给同学
据魔方格专家权威分析，试题“三个质数之和是86，那么这三个质数是______．-数学-魔方格”主要考查你对&&有理数定义及分类&&等考点的理解。关于这些考点的“档案”如下：
现在没空？点击收藏，以后再看。
因为篇幅有限，只列出部分考点，详细请访问。
有理数定义及分类
有理数的定义：有理数是整数和分数的统称，一切有理数都可以化成分数的形式。有理数的分类：（1）按有理数的定义：&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&正整数&&&&&&&&&&&&&&&&& 整数{&&&& 零&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &负整数 有理数{&&&&& &&&&&&&&&&&&&&&&&&&&&&&& && 正分数&&&&&&&&&&&&&&&&&分数{ &&&&&&&&&&&&&&&&&&&&&&&&&&& 负分数 &（2）按有理数的性质分类:&&&&&&&&&&&&&&&&&&&&&&&&&&&&正整数&&&&&&&&&&&&&&&& 正数{&&&&&&&&&&&&&&&&&&&&&&&&&&&&正分数 有理数{& 零&&&&&&&&&&&&&&&&&&&&&&&&&&&负整数&&&&&&&&&&&&&&&&负数{ &&&&&&&&&&&&&&&&&&&&&&&&& &负分数
发现相似题
与“三个质数之和是86，那么这三个质数是______．-数学-魔方格”考查相似的试题有：
7420757237383678496951944250667107332002年9月 C++ Builder大版内专家分月排行榜第三
2002年5月 专题开发/技术/项目大版内专家分月排行榜第二2002年2月 专题开发/技术/项目大版内专家分月排行榜第二2001年11月 专题开发/技术/项目大版内专家分月排行榜第二2001年7月 专题开发/技术/项目大版内专家分月排行榜第二
2002年6月 专题开发/技术/项目大版内专家分月排行榜第三
2002年5月 专题开发/技术/项目大版内专家分月排行榜第二2002年2月 专题开发/技术/项目大版内专家分月排行榜第二2001年11月 专题开发/技术/项目大版内专家分月排行榜第二2001年7月 专题开发/技术/项目大版内专家分月排行榜第二
2002年6月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。当前位置 & &
& 为什么数学家对质数如此着魔？
为什么数学家对质数如此着魔？
19:19:55&&出处：&&作者：Dillan
编辑：上方文Q &&)
让小伙伴们也看看：
阅读更多：
好文共享：
文章观点支持
当前平均分：0(0 次打分)
[11-02][11-01][10-12][10-08][09-13][09-09][08-27][08-15][07-28][07-18]
登录驱动之家
没有帐号？
用合作网站帐户直接登录