安全检查中...
请打开浏览器的javascript，然后刷新浏览器
< 浏览器安全检查中...
还剩 5 秒&博客分类：
自然数是0，1，2……
素数是2，3，5……（不包括1的只能背1和它本身整除的自然数）
#include&stdio.h&
#include &math.h&
void main()
int i ,j, flag=1;
for(i=101; i&200; i++)
for(j=2; j&=sqrt(200); j++)
if(i%j == 0){
if(flag == 1)
printf("i=%d是素数\n",i);
【1】求10000以内的所有素数。素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。像著名的 哥德巴赫猜想、孪生素数猜想，几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研，呕心沥血，但至今仍然未见分晓。自从有了计算机之后，人们借助于计算机的威力，已经找到了2216091以内的所有素数。求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不必再用其他的数去除。第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明：如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。如果d1和d2均大于√N，则有：N＝d1×d2&√N×√N＝N。而这是不可能的，所以，d1和d2中必有一个小于或等于√N。基于上述分析，设计算法如下：(1)用2，3，5，7逐个试除N的方法求出100以内的所有素数。(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100，就依次存放在A数组中的一个单元 中。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N，这个范围内的素数可以不保存，直接打印。【2】用筛法求素数。简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的各数写在纸上：
在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数。
这很像一面筛子，把满足条件的数留下来，把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的，所以，后人就把这种方法称作厄拉多塞筛法。在计算机中，筛法可以用给数组单元置零的方法来实现。具体来说就是：首先开一个数组：a[i]，i=1，2，3，…，同时，令所有的数组元素都等于下标 值，即a[i]=i，当i不是素数时，令a[i]=0 。当输出结果时，只要判断a[i]是否等于零即可，如果a[i]=0，则令i=i+1，检查下一个a[i]。筛法是计算机程序设计中常用的算法之一。【3】用6N±1法求素数。任何一个自然数，总可以表示成为如下的形式之一：6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)显然，当N≥1时，6N，6N+2，6N+3，6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数)。根据上述分析，我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选，这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度。在程序上，我们可以用一个二重循环实现这一点，外循环i按3的倍数递增，内循环j为0－1的循环，则2(i+j)-1恰好就是形如6N±1的自然数。
注意: 如果没有特殊说明, 以下讨论的都是针对n为素数时的时间复杂度1. 根据概念判断:如果一个正整数只有两个因子, 1和p，则称p为素数.
代码: 时间复杂度O(n).
bool isPrime(int n)
for(int i = 2; i & ++i)
if(n%i == 0)
2. 改进, 去掉偶数的判断
代码: 时间复杂度O(n/2), 速度提高一倍.
bool isPrime(int n)
if(n == 2)
for(int i = 3; i & i += 2)
if(n%i == 0)
3. 进一步减少判断的范围定理: 如果n不是素数, 则n有满足1&d&=sqrt(n)的一个因子d.证明: 如果n不是素数, 则由定义n有一个因子d满足1&d&n.如果d大于sqrt(n), 则n/d是满足1&n/d&=sqrt(n)的一个因子.
代码: 时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).
bool isPrime(int n)
if(n == 2)
for(int i = 3; i*i &= i += 2)//使用 i&sqrt(n)
if(n%i == 0)
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, temp = 2; temp & i += 2)
int flag =
for(j = 1; primes[j]*primes[j] &= ++j)
if(i%primes[j] == 0)
primes[temp++] =
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) = /(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[6542+1];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 bool 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分法查找在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)
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个素数!
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,
因此, 我只需要把前46个Fibonacci数保存到数组中就可以搞定了!比如: F(int i) = {return Fibonacci[i];} 非常简单, 效率也非常好.
tracyhuyan
浏览: 50691 次
来自: 深圳
去这里看看吧 收集素材更方便 http://www.sucai ...
很好，总结了素数的算法以及时间复杂度。笑纳了！
这部电影了。& & & & & & & & & & & & &素数筛法
基本概念：
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为质数。
而在ACM比赛当中经常遇到需要使用大量既定的素数，或者判定素数，或者应用于唯一分解定理当中。
介绍与证明：
厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的各数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于
这很像一面筛子，把满足条件的数留下来，把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的，所以，后人就把这种方法称作厄拉多塞筛法。
在计算机中，筛法可以用给数组单元置零的方法来实现。具体来说就是：首先开一个数组：a[i]，i=1，2，3，…，同时，令所有的数组元素都等于下标&#20540;，即a[i]=i，当i不是素数时，令a[i]=0
。当输出结果时，只要判断a[i]是否等于零即可，如果a[i]=0，则令i=i&#43;1，检查下一个a[i]。
筛法是计算机程序设计中常用的算法之一。
算法实现：
&如果要是按照一个一个判断是否是素数，时间复杂度为O(n√n)，对于10^6的数据时间复杂度就是O(10^9)，必定会TLE，但此时“筛法”的时间复杂度只有O(nloglogn)。（埃拉托斯特&#23612;的方法叫做“埃拉托斯特&#23612;筛法”，简称“筛法”）
（1）最初的筛法：
可输入实现版：
#include&iostream&
#include&cmath&
#include&cstring&
#define maxn 100005
int prime[maxn];
//第i个素数
bool isprime[maxn+10];
int main()
while(cin&&n)
memset(isprime,1,sizeof(isprime));
isprime[0]=isprime[1]=0;
for(int i=2; i&=n; i++)
if(isprime[i])
prime[++p]=i;
for(int j=2*i; j&=n; j+=i)
isprime[j]=0;
for(int i=0; i&=n; i++)
cout&&isprime[i];
核心代码段：
memset(isprime,1,sizeof(isprime));
isprime[0]=isprime[1]=0;
for(int i=2; i&=n; i++)
if(isprime[i])
prime[++p]=i;
for(int j=2*i; j&=n; j+=i)
isprime[j]=0;
手动地模拟原始筛法就可以发现，某个数字可能被不止一次地删去，我们可以进一步优化，去除不必要的重复。
（2）优化后的筛法：
可输入实现版：
#include&iostream&
#include&cmath&
#define maxn 100005
bool isprime[maxn];
int prime[maxn];
//第i个素数
int main()
while(cin&&n)
isprime[0]=isprime[1]=0;
isprime[2]=1;
for(int i=3; i&=n; i++)
isprime[i]=i%2==0?0:1;
int tmp=(int)sqrt(n+0.5);
for(int i=0; i&= i++)
if(isprime[i])
prime[++p]=i;
for(int j=i*i; j&n; j+=2*i)
isprime[j]=0;
for(int i=0; i&=n; i++)
cout&&isprime[i];
核心代码段：
isprime[0]=isprime[1]=0;
isprime[2]=1;
for(int i=3; i&=n; i++)
isprime[i]=i%2==0?0:1;
int tmp=(int)sqrt(n+0.5);
for(int i=0; i&= i++)
if(isprime[i])
prime[++p]=i;
for(int j=i*i; j&n; j+=2*i)
isprime[j]=0;
*&还有其他类型的筛法，比如说二次筛法，数域筛法等，这里就不提及了。
推荐习题： HDU2012 、 HDU3792
~step by step
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：988次
排名：千里之外
原创：18篇
(2)(2)(16)(3)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
这是书中的原文:
厄拉多塞筛法是一种用于计算小于N的所有素数的方法. 我们从制作整数2到N的表开始. 找出最小的未被删除的整数i,然后删除i,2i,3i.... 当i&√N时, 算法终止
答案是NloglogN, 却没有说具体是怎么算的.
上网找了好久, 都是只有结论, 没有讲如何算出来的.
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
O(NloglogN)数的是算术运算的次数。当N很大时，每个算术运算不一定在常数个指令周期内完成。不妨假设算术运算的时间复杂度是O(logN)，也就是存储N所需要的空间。
此时厄拉多塞筛法的时间复杂度是O(NloglogN) * O(logN) = O(NlogNloglogN)。
而这个loglogN又是怎么来的呢？厄拉多塞筛法找到k的时候需要标记O(N/k)个数为合数。因此一共需要标记 次，其中p &= N表示所有小于等于N的素数。这就是N乘以小于等于N的素数的倒数之和。
同步到新浪微博
分享到微博？
Hi，欢迎来到 SegmentFault 技术社区！⊙▽⊙ 在这里，你可以提出编程相关的疑惑，关注感兴趣的问题，对认可的回答投赞同票；大家会帮你解决编程的问题，和你探讨技术更新，为你的回答投上赞同票。
明天提醒我
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：素数的判定与筛法
& & 判定：很简单嘛！暴力大法参上！
#include&iostream&
#include&cmath&
unsigned long int n,i,j,a,b;
int main()
j=(int)sqrt(n);
for(i=2;i&=j;i++)
if(n%i==0)
if(i&j&&n!=0&&n!=1) cout&&"Yes";
else cout&&"No";
& & &（不相信从来不刷水的我竟然做了这样的题&&）
& & & 这就是传说中的O(根号N)大暴力&&
& & & 那么还有个算法叫Miller-rabin&&
那么我们来介绍一下这是个什么东西：
& & & 首先让我们了解这几个概念：
& & & 费马小定理：对于素数p和任意整数a，有ap&& a(mod p)（同余）。反过来，满足ap&& a(mod p)，p也几乎一定是素数。
　　伪素数：如果n是一个正整数，如果存在和n互素的正整数a满足 an-1&& 1(mod n)，我们说n是基于a的伪素数。如果一个数是伪素数，那么它几乎肯定是素数。
　　Miller-Rabin测试：不断选取不超过n-1的基b(s次)，计算是否每次都有bn-1&& 1(mod n)，若每次都成立则n是素数，否则为合数。　
& & &设待测数为n，取一个比n小的正整数a,设n-1=d*2^r。若n是素数，则要么a^d mod n = 1,要么存在一个i,满足0&i＜r且a^(d*2^i )mod n = -1
& &&经过独立的t轮Miller-Rabin算法将一个合数误判为素数的可能性不大于 (1/4)t，(正确实现的算法不会误判素数为合 数)，这个误判概率在基于Fermat定理的算法中是最好的。一轮Miller-Rabin算法的最坏情况时间复杂度为 (1+O(1))log2(n)( 以模n乘法为基本操作)。如果以单精度乘法操作作为时间复杂度的衡量，则一轮优化的Miller-Rabin算法的最 坏情况时间复杂度为O(log32 (n) 。从时间复杂度来看Miller- Rabin算法的性能是很好的。在实际应用中，Miller-Rabin 算 法的实际执行速度也很快。
& & &大家可以多次调用该函数，使得错误率降低。
#include&stdio.h&
#include&stdlib.h&
#include&cmath&
bool witness(__int64 a,__int64 n)
__int64 t,d,x;
int i=ceil(log(n-1.0)/log(2.0)) - 1;
for(;i&=0;i--)
d=(d*d)%n;
if(d==1 && x!=1 && x!=n-1)
if( ((n-1) & (1&&i)) & 0)
d=(d*a)%n;
return d==1? false :
bool miller_rabin(__int64 n)
if(n==1 || ((n&1)==0))
for(int i=0;i&50;i++){
__int64 a=rand()*(n-2)/RAND_MAX +1;
if(witness(a, n))
int main()
while(scanf("%d",&n)!=EOF)
while(n--)
scanf("%I64d",&a);
if(miller_rabin(a))
printf("%d\n",cnt);
筛法：筛法有3种时间复杂度，详细说应该有四种，最后一种貌似是打表&&
& & & & & & & &1.O(N*根号N)
& & & & & & & &2.O(NlogN)
& & & & & & & &3.O(N)
& & & & & & &&
& & & & & & & &第一种方法：很明显的暴力啊&&循环+判断
& & & & & & & &第二种方法：这是比较常用的一种筛法：埃氏筛（俗称垃圾筛），根本思想很简单：我们从1往N搜，假如我们遇到了一个没有被标记为不是素数的数，那么我们把它的倍数（&1）都标记为非素数&&
& & & & & & & &
for(int i=2;i&=1000000;i++)
if(!FP[i])
PL[++e]=i;
for(long long j=(long long)i*i;j&=1000000;j+=i) FP[j]=1;
　　 & & & &第三种方法：线性筛，这个还是根据代码来解释吧&&
& & & & & & & &第一行：应该没必要解释吧
& & & & & & & &第二行：从1到N枚举
& & & & & & & &第三行：同埃氏筛
& & & & & & & &第四行：枚举素数
& & & & & & & &第五行：如果乘上i大于n了，那么后面也肯定大于n，so break&&
& & & & & & & &第六行：把prime[j]的i倍标记为不是素数
& & & & & & & &第七行：这个是代码的核心句，如果没有这句，那么它的时间复杂度与埃氏筛一样，但是我们来看一看12，它是在什么时候被枚举到的？第6次循环，也就是说，我们这次如果不加这条语句，那么有写情况是算重复了，那么这条鱼句就可以保证它不会重复。
& & & & & & & &1. 任何一个合数都可以表示成一个质数和一个数的乘积& & & & & & & &2. 假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积& & & & & & &例如: 如果i = 8; 那么由于i%2 == 0; 因此对于i=8就只需要检查primes[1]=2即可，因为对于大于primes[1]的质数，像3，有:8*3 = 2*4*3 = 12*2& & & & & & & 也就是说24(8*3=24)并不需要在8时检查，在12时才检查
阅读(...) 评论()}