目录

一、素数及相关概念

 1、素数的性质

 2、有关素数的猜想

 二、素数的判断方法

 1、根据性质去判断

 2、改进1方法（缩小比较范围√n）

3、再次分析素数的特点，得出规律

问题：枚举n以内所有素数

 4、埃氏筛法（埃拉托斯特尼筛法）

5、欧拉筛法（埃氏筛法的优化版）

三、素数相关题目

一、素数及相关概念

素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是质数也不是合数）。

 1、素数的性质

质数只有两个因数：1和本身。任何大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。质数的个数是无限多的。若n为正整数，在n²到(n+1)²之间至少有一个质数若n为大于等于2的正整数，则n到n!之间至少有一个质数若质数p为不超过n(n≥4)的最大质数，则p＞n/2所有大于10的质数中，个位数只有1，3，7，9在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。存在任意长度的素数等差数列。

 2、有关素数的猜想

哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？斐波那契数列内是否存在无穷多的素数？是否有无穷多个的梅森素数？（所谓梅森数，是指形如2ᵖ－1的一类数，其中指数p是素数，常记为Mp。如果梅森数是素数，就称为梅森素数。）是否存在无穷个形式如X2+1素数？

 趣味数学

 3到881之内的孪生素数

2至54的素数

 二、素数的判断方法

 1、根据性质去判断

我们都知道素数的性质是除了1和它自身外，不能被其他自然数整除，所以第一个方法就是从2到n-1一个个去判断是否有数可以除以该数且为0,即 n%i==0；如果有则不是素数，如果遍历一遍都没有数可以整除它，则就是素数。

public class Main {    public static boolean isPrime(int n){        if (n <= 3) {            return n > 1;        }        for (int i=2;i<n;i++){            if (n%i==0)                return false;        }        return true;    }    public static void main(String[] args) {       for (int i=2;i<100;i++){//找2到100之间的素数           if (isPrime(i))                System.out.print(i+" ");           //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       }    }}

 2、改进1方法（缩小比较范围√n）

看了方法一，大家觉得浪费了很多时间，不必一直循环到n-1，因为如果a*b=n，则其中必有一个大于sqrt(n) ，一个小于sqrt(n),，所以我们把循环范围缩小到√n。

public class Main {    public static boolean isPrime(int n){        if (n <= 3) {            return n > 1;        }        for (int i=2;i<=Math.sqrt(n);i++){            if (n%i==0)                return false;        }        return true;    }    public static void main(String[] args) {       for (int i=2;i<100;i++){//找2到100之间的素数           if (isPrime(i))                System.out.print(i+" ");           //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       }    }}

3、再次分析素数的特点，得出规律

其实素数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。
这个结论其实很容易论证。首先 6x 肯定不是质数，因为它能被 6 整除；然后6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (相当于6x-1) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。我们也可以通过孪生素数可以很清楚的验证这个规律。

 这样我们又可以更加便捷的找出想要找的素数。

public class Main {    public static boolean isPrime(int num) {        if (num <= 3) {            return num > 1;        }        // 不是在6的倍数两侧的一定不是素数数        if (num % 6 != 1 && num % 6 != 5) {            return false;        }        //同样的在6的倍数两侧的数也不一定是素数，还是要判断        int sqrt = (int) Math.sqrt(num);        for (int i = 5; i <= sqrt; i += 6) {            if (num % i == 0 || num % (i + 2) == 0) {                return false;            }        }        return true;    }    public static void main(String[] args) {       for (int i=2;i<100;i++){//找2到100之间的素数           if (isPrime(i))                System.out.print(i+" ");           //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       }    }}

问题：枚举n以内所有素数

上面方法都是用来判断是不是,但是当叫你求n内素数的个数时，这样一个个去判断的时间复杂度过大，太费时间，这就需要下面的方法了。

 4、埃氏筛法（埃拉托斯特尼筛法）

埃氏筛法就是先把所有整数列出来，然后把2的倍数全部剔除，然后是三的，以此类推，遍历所有素数，把倍数全部划去。对于某个数字i，如果没被划去，他一定是素数，因为他不是任何2到i-1数字的倍数。然后就开始划它的倍数就好。

import java.util.Arrays;public class Main {    static int isPrime(int n)    {        int[] b=new int[n+1];//通过数组b的值，为1就是素数        int p=0;//记录素数个数        for(int i=0;i<n+1;i++)            b[i]=1;        b[0]=0;        b[1]=0;        //准备完毕        for(int i=2;i<=n;i++){            if(b[i]!=0){                p++;//i是素数即i++;然后剔除i的倍数                for(int j=2*i;j<=n;j+=i)                    b[j]=0;//剔除倍数            }        }        return p;//返回素数个数    }    public static void main(String[] args) {       //找2到100之间的素数        System.out.print(isPrime(100));//25        //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       }}

或者使用boolean值来进行辨别是否为素数，我们可以埃氏筛法把所有素数找出来，然后继续O（1）操作来判断i是否为素数。

public class Main {    public static void main(String[] args) {        boolean[] isPrime=new boolean[100+1];  //true为素数        isPrime[0]=false;        isPrime[1]=false;        for (int i=2;i<100+1;i++) isPrime[i]=true;        for (int i=2;i<100+1;i++){            if (isPrime[i]){                for (int j=2;i*j<100+1;j++)                    isPrime[i*j]=false;            }        }    }}

 很上面一样可以进行优化不必一直循环到n，到Math.sqrt(n)就可以。

public class Main {     public static void main(String[] args) {        boolean[] isPrime=new boolean[100+1];  //true为素数        isPrime[0]=false;        isPrime[1]=false;        for (int i=2;i<100+1;i++) isPrime[i]=true;        for (int i=2;i<Math.sqrt(101);i++){            if (isPrime[i]){                for (int j=2;i*j<100+1;j++)                    isPrime[i*j]=false;            }        }        for (int i=2;i<isPrime.length;i++){            if (isPrime[i])                System.out.print(i+" ");            //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         }    }}

5、欧拉筛法（埃氏筛法的优化版）

在埃氏筛法中，由于一个数可以既是一个素数的倍数，又是另一个素数的倍数，可以发现这会出现重复标记的情况，即同一个数被筛掉了不止一次，如果n值过大，则也是一笔不小的时间开销。

欧拉筛法就是在埃氏算法的基础上多了判断的步骤，从而消去了这种重复标记的情况，核心思路是用合数中的一个因数筛掉这个合数。

public static void eulerSieve(int n){        boolean[] isPrime = new boolean[n+1];         int[] Prime=new int[n];//存放素数的数组，false为素数        isPrime[0] = isPrime[1] = true;//数字0和1都不是素数，所以赋true        int count = 0;        Prime[count++] = 2;//把2放进素数表        for (int i = 2; i <n+1; i++) {            if (!isPrime[i])//若当前数是素数                Prime[count++] = i;//则存入素数数组            for (int j = 0; j < count && Prime[j] * i < n+1; j++) {                isPrime[i * Prime[j]] = true;                if (i % Prime[j] == 0)                    break;//避免重筛,使得程序更有效率            }        }    }

可以看 欧拉筛法寻找10以内的素数，可以发现完全没有重复判断的数，因为多了一个判断，大幅增加了筛素数的速度，时间复杂度为O（n）。

三、素数相关题目

蓝桥杯之找素数（填空题+编程题）_冷兮雪的博客-CSDN博客