蓝桥杯之素数及相关判断方法（看这一篇就够了）-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯之素数及相关判断方法（看这一篇就够了）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、素数及相关概念

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;//避免重筛,使得程序更有效率
            }
        }
    }