素数的概念

素数的判断⽅法（从⼀般到⾼效）

1.素数判定问题

素数判定问题是⼀个⾮常常见的问题，本⽂介绍了常⽤的⼏种判定⽅法。

2.直观判断

素数的定义是，除了能被1和它本⾝整除⽽不能被其他任何数整除的数。根据素数定义只需要⽤2到n-1去除n，如果都除不尽，则n是素数，否则，只要其中有⼀个数能

整除则n不是素数。

1boolprime_1(intn){

2for(inti=2;i

3if(n%i==0)

4returnfla;//不是素数

5}

6el

7returntrue;//是素数

8}

3.直观判断改进

上述判断⽅法，明显存在效率极低的问题。对于每个数n，其实并不需要从2判断到n-1，我们知道，⼀个数若可以进⾏因数分解，那么分解时得到的两个数⼀定是⼀个

⼩于等于sqrt(n)，⼀个⼤于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也⼀定找不到约数。C++代码

如下：

1boolprime_2(intn){

2for(inti=2;i<=sqrt(n);i++)

3if(n%i==0)

4returnfla;//不是素数

5el

6returntrue;//是素数

7}

3.筛法求素数

更⾼效地素数判断⽅法应该是将素数预先保存到⼀个素数表中，当判断⼀个数是否为素数时，直接查表即可。这种⽅法需要解决两个问题：

(1)怎样快速得到素数表？（采⽤筛选⽅法）

(2)怎样减少素数表的⼤⼩？（采⽤位图数据结构）

对于1到n全部整数，逐个判断它们是否是素数，找出⼀个⾮素数，就把它挖掉，最后剩下的就是素数。具体⽅法是：

<1>定义is_primer[i]=true;

<2>从2开始，依次遍历整个primer(直到sqrt(N))，如果primer[i]=true,则primer[n*i]=fal

如1,2,3,4,5,6,7,8,9,10，则

从2开始遍历：

primer[2]=true，则primer[4]=primer[6]=primer[8]=primer[10]=fal，2的倍数

primer[3]=true，则primer[6]=primer[9]=fal，3的倍数

1#include

2#defineM2000000

3charA[2000000]={"0"};

4intS[150001]={0};

5intmain()

6{

7intm,n,i,j,k=0;

8for(i=2;i

9if(!A[i])

10{

11for(j=i+i;j

12A[j]=1;

13S[++k]=i;

14}

15for(i=0;i<150001;i++)

16printf("%dt",S[i]);

17return0;

18}

1//筛法求素数，哈希表查找

2#include

3#defineMAX2000000

4intprime[2000000];

5intmain(){

6for(inti=2;i<=MAX;i++)

7prime[i]=1;

8prime[1]=0;

9for(inti=2;i<=MAX;i++)//打表

10for(intj=2*i;j<=MAX;j+=i)

11prime[j]=0;//偶数标记0

15for(inti=2;i<=2000000;i++)

16if(prime[i]==1)

17printf("%dt",i);//输出素数

18return0;

19}

⾄今为⽌，没有任何⼈发现素数的分布规律，也没有⼈能⽤⼀个公式计算出所有的素数。关于素数的很多的有趣的性质或者科学家的努⼒，

如：

(1)⾼斯猜测，n以内的素数个数⼤约与n/ln(n)相当，或者说，当n很⼤时，两者数量级相同。这就是著名的素数定理。

(2)⼗七世纪费马猜测，2的2^n次⽅+1，n=0，1，2…时是素数，这样的数叫费马素数，可惜当n=5时，2^32+1就不是素数，⾄今也没有找

到第六个费马素数。

(3)18世纪发现的最⼤素数是2^31-1，19世纪发现的最⼤素数是2^127-1，20世纪末⼈类已知的最⼤素数是2^859433-1，⽤⼗进制表⽰，这

是⼀个258715位的数字。

(4)孪⽣素数猜想：差为2的素数有⽆穷多对。⽬前知道的最⼤的孪⽣素数是1159142985×2^2304－1和1159142985×2^2304＋1。