判断素数的五种方法最全埃筛素数欧筛素数孪生素数

前言：
判断素数是编程中经常应用的实例，是编程学习的重要知识，那么下面我将介绍五种判断素数的方法。
定义：
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
简单来说就是，如果一个数只能被1和它本身整除，那么这个数就是素数。
比如：2 3 5 7 11 23…
0和1既不是素数也不是合数，2是最小的素数。

方法（一）暴力法
最简单最暴力的方法就是根据定义，判断n是不是素数，则把1~n
内所有数都遍历，若都不能整除则为素数。因为如果n为素数，则只有1和n为因数。
代码如下：

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,b=1;
    scanf("%d",&n);
    for(int i = 2;i < n;i++){
        if(n % i == 0){
            b = 0;  break;
        }
    }
    if(b == 0){ printf("%d不是素数",n); }
    if(b == 1){ printf("%d是素数",n);   }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法（二）优化
上述方法效率极低，如果n为一万，则核心代码要跑n-2次，其实我们只需要判断2~√n个数，因为一个数如果可以因数分解（不是质数），那么分解得到的两个数一定是一个小于等于√n，一个大于等于√n，一个合数一定由两个自然数相乘，一个大于等于平方根一个小于等于平方根，并且成对存在，所以只判断前根号个。这时我们需要使用sqrt函数来求根号。
代码如下：

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
    int n,b=1;
    scanf("%d",&n);
    for(int i = 2;i < sqrt(n);i++){
        if(n % i == 0){
            b = 0;   break;
        }
    }
    if(b == 0){  printf("%d不是素数",n); }
    if(b == 1){  printf("%d是素数",n); }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法（三）孪生素数法
结论1：
当n>=5时，不在6x（x≥1）两侧的肯定不是素数，但在6x（x>=1）两侧的并不是一定就是素数。意思6x-1和6x+1可能为素数。

证明：

当n>=5时，若n为素数，n一定出现在6x（x>=1）的两侧。

6x-2 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1)…

观察得： 6x-2 = 3(x-1)，6x = 2(3x)，6x+2 = 2(x+1) …显然他们都不是素数

所以当n>=5时，素数一定在6x两边。

但是当x = 9时，6(x+1) = 55，可以被5整除，所以6x两侧不一定是素数。

结论2：
若n≥6且n-1和n+1为孪生素数，那么n一定是6的倍数。

证明：
因为孪生素数是差值为2的相邻素数。所以n-1和n+1是素数(小结论1)

所以 n-1和n+1一定是奇数，则n是偶数，所以n是2的倍数 (小结论2)

我们再假设n不是3的倍数，则n = 3x+1 或 n = 3x+2，

如果n = 3x+1，则n-1=3x，n-1可能为偶数，与小结论1违背

如果n = 3x+2，则n+1=3(x+1)，n+1可能是偶数，与小结论2违背

所以n不是3的倍数不成立，

所以n是3的倍数，又结合小结论2：

n是一定是6的倍数，所以代码增量为6，再判断n+1和n-1是否可以
于是乎代码如下：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int su(int n){
    if(n < 5){
    if(n == 2 || n == 3) return 1;
    else  return 0;
     }
    else {
        if(n%6!=1 && n%6!=5)
            return 0;
        else {
            for(int i=5;i<=sqrt(n);i+=6){
                if(n%i==0 || n%(i+2)==0)
                    return 0;
            }
            return 1;
        }
    }
}
int main()
{
    int n,b;
    scanf("%d",&n);
    b = su(n);
    if(b == 0){  printf("%d不是素数",n); }
    if(b == 1){  printf("%d是素数",n);   }

    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法（四）埃筛法
埃筛很简单，因为素数只能被1或者它本身整除，所以一个数的倍数一定不是素数，下面举个栗子：

2 为素数，则4 6 8 10 12 14 16等都不是素数

如此简但，直接上代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    int n,i,j;
    scanf("%d",&n);
    int vis[100000]={1,1};//0和1不是素数其他先默认为0
    for(i=2;i<100000;i++){
        if(vis[i]==0){
            for(j=i+i;j<10000;j+=i){
                vis[j]++;
            }
        }
    }
    if(vis[n]==0)printf("%d是素数",n);
    else printf("%d不是素数",n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法（五）欧式筛法
欧式筛法是埃筛的改进，相信大家一定注意到了埃筛的小问题
当i = 2时 我们遍历了4 6 8 10 12
当i = 3时 我们遍历了6 9 12 15

我们发现了6和12被重复筛出，这样的例子数不胜数，大大降低了效率

现在我们伟大的欧拉函数来了，数学的魅力就这里绽放

1：任何一个合数都可以分解成一个素数×一个数

2：i = m * n，m是最小质因子(素数=质数)

若n为合数，n= x*y，x是一个质数，且x>m

则i = mn = mxy = xmy，且my = k.

则i = x*k，且 x>m

说明一个合数与一个质数的乘积，可以表示为一个更大的合数和一个更小的质数的乘积。

代码如下：
输入一个n，打印出以内所有素数。

#include<stdio.h>
#include<stdlib.h>
int su[1000000];
int prime[10000];
int main()
{
    int i,j,n,s=0;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        if(su[i] == 0){
            prime[++s] = i ;
        }
        for(j=1;j<=s && i*prime[j]<=n;j++){
            su[i*prime[j]] = 1 ;
            if(i%prime[j] == 0) break;
        }
    }
    for(i=1;i<=s;i++){
        printf("%d ",prime[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23