计算质数【Java】

妖狐艹你老母 2023-09-26 19:59 110阅读 0赞

#### 文章目录 ####

*  暴力迭代法
 *  迭代优化版
 *  埃氏筛法
 *  结尾

**质数**

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

那么如何计算一个数是否为质数呢？本文提供以下几种方法。

## 暴力迭代法 ##

> 判断 i 是否为素数，从2开始遍历，直到 i-1 的数，每个数字都判断一个是否能整除 i ，如果可以，那么 i 就不是质数，如果没有一个数能整除 i ，那么 i 就是质数。

**统计十万以内的素数个数**

public class Test {
        
        public static void main(String[] args) {
        
            int n=100000;
            int count=0;
    
            long start = System.currentTimeMillis();    //返回以毫秒为单位的当前时间
    
            for(int i=2; i<n; ++i){
        
                boolean flag=true;
                for(int j=2; j<i; ++j){
        
                    if((i%j) == 0){
        
                        flag=false;
                        break;
                    }
                }
                if(flag == true){
        
                    ++count;	// 记录个数
                }
            }
            long end = System.currentTimeMillis();
    
            System.out.println("耗时："+(end-start)+"毫秒");
            System.out.println("小于"+n+"的素数总共有"+count+"个");
        }
    }

**运行结果**

**平均耗时1.5秒**  
![在这里插入图片描述][e3dff7fc6c4c4a36a443e9d01071b739.png]

## 迭代优化版 ##

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

上面的方法其实是可以被优化，先说结论：`如果一个数，不是质数，那么它一定有一个因数小于等于这个数的开平方根，一个因数大于等于这个数的开平方根。`

`例如：a=x*y，a不是质数，那么它一定有一个因数小于等于√a，一个因数大于等于√a。`

`因为因数是成对出现的，如果有数 m=x*y ，那么x与y之间必然是一个 >= √m，一个 <= √m，因为（√m * √m）等于 m，那么如果x、y都小于 √m，那这两个数乘积也一定小于m，如果x、y都大于√m，那这两个数的乘积也一定大于m。`

所以由此可以证明，如果数m不是质数，那么它的两个因数必然有一个小于等于√m，那么上面的代码就要改为只遍历到开平方根即可，减少不必要的循环次数。

**Code**

public class Test {
        
        public static void main(String[] args) {
        
            int n=100000;
            int count=0;
    
            long start = System.currentTimeMillis();    //返回以毫秒为单位的当前时间
    
            for(int i=2; i<n; ++i){
        
                boolean flag=true;
                for(int j=2,dest=(int)Math.sqrt(i); j<=dest; ++j){
        
                    if((i%j) == 0){
        
                        flag=false;
                        break;
                    }
                }
                // 记录个数
                if(flag == true){
        
                    ++count;
                }
            }
    
            long end = System.currentTimeMillis();	//返回以毫秒为单位的当前时间
    
            System.out.println("耗时："+(end-start)+"毫秒");
            System.out.println("小于"+n+"的素数总共有"+count+"个");
        }
    }

**运行结果**

**优化后的代码可以看出非常明显的耗时对比，优化后的平均耗时0.012秒，两者之间的效率差会随着n的增大而增大。**  
![在这里插入图片描述][ef9514d391614ffa8e0ce6a966e5657b.png]

## 埃氏筛法 ##

虽然上面的代码经过了优化之后，效率提升了很多，但是如果在n很大的时候，速度还是不可避免地慢下来。

**例如下面这道题目，n的范围在\[0,5000000\]这个区间内，那么当给定的n很大时，优化版的代码虽然能在本地ide上跑过，但是当有限制了程序运行时间的时候，就可能会超过这个限制，导致题目的不通过。**

![在这里插入图片描述][e5afed9850ba43479668a96ae13d7078.png]

**优化版代码的运行结果**  
虽然答案正确，但是不符合限定的运行时间。导致无法通过。  
![在这里插入图片描述][0bd91ee8e3b1412c9b420d8c02b714fe.png]

那么是否有一种更高效的算法呢？`埃氏筛法。`  
![该图来自百度百科][e9e25e01b5f04654a406fe47c8d0dbbd.png]

> 该图来自网络，侵删

要得到自然数n以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。
    给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；
    再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；
    接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

**简单的来说就寻找到一个质数x之后，将就x的倍数给去掉，因为x的倍数可以被x整除，那么x的倍数肯定不是质数，最后留下的就是质数。**  
那我们只需要将没去除的数记录下来即可，每个数字只需检查是否被标记即可。

**具体流程图**

![在这里插入图片描述][c36386ace0b94b3c9e637a053fcab16e.gif_pic_center]  
**该图片来自leetcode用户：Sweetiee ，侵删**

**Code**

class Solution {
        
    	//给定一个n，求小于n的质数个数
        public int countPrimes(int n) {
        
        
            int res=0;
            boolean[] flag=new boolean[n];  //申请n个大小空间的标记位
            for(int i=2; i<n; ++i){
        
                // boolean类型初值为false
                if(!flag[i]){
        
                    ++res;  //记录个数
                    // 放置溢出
                    if((long)i*i < n){
        
                        for(int j=i*i; j<n; j+=i){
        
                            flag[j]=true;
                        }
                    }
                }
            }
            return res;
        }
    }

内循环为什么可以从i*i开始呢，因为在i*i之前的数字已经被比i小的数筛选过了。
    例如数3，内循环是从9开始的，那么3-9之间的数字呢？
    比如7，如果7不是一个质数，那么一定会被2给筛去。
    因为任意的素数x倍数有：2x、3x、4x、...、x*x、(x+1)*x、...
    任意小于x*x的倍数已经被之前的素数筛去了，比如2筛去了 2x、4x 、... 
    所以，内循环只需要从i*i开始即可。

**运行结果**

可以看出利用埃氏筛法的方式解这道题是可以通过的，具体运行时间，各位可以拿上面迭代的模板改一下求得，可以拿同等数据量的情况下来对比一个迭代法与埃氏筛法的效率。  
![在这里插入图片描述][60bee66f38b74f6c93f11d82d4da0773.png]

## 结尾 ##

利用埃氏筛法求质数已经算是很高效了，但是还是会有重复标记的情况，比如数16，会被2标记一次，还会被4标记一次，数字越大重复标记的次数越多，从上面的代码运行图也可以看出来，那能否去掉重复标记的情况呢，有一种算法名为欧拉筛法，也是用于求质数的，这种算法就排除了重复标记的情况，不过目前我也还不会，等我学会了再与各位分享吧。  
就这样，如有错误，望指出。

[e3dff7fc6c4c4a36a443e9d01071b739.png]: https://img-blog.csdnimg.cn/e3dff7fc6c4c4a36a443e9d01071b739.png
[ef9514d391614ffa8e0ce6a966e5657b.png]: https://img-blog.csdnimg.cn/ef9514d391614ffa8e0ce6a966e5657b.png
[e5afed9850ba43479668a96ae13d7078.png]: https://img-blog.csdnimg.cn/e5afed9850ba43479668a96ae13d7078.png
[0bd91ee8e3b1412c9b420d8c02b714fe.png]: https://img-blog.csdnimg.cn/0bd91ee8e3b1412c9b420d8c02b714fe.png
[e9e25e01b5f04654a406fe47c8d0dbbd.png]: https://img-blog.csdnimg.cn/e9e25e01b5f04654a406fe47c8d0dbbd.png
[c36386ace0b94b3c9e637a053fcab16e.gif_pic_center]: https://img-blog.csdnimg.cn/c36386ace0b94b3c9e637a053fcab16e.gif#pic_center
[60bee66f38b74f6c93f11d82d4da0773.png]: https://img-blog.csdnimg.cn/60bee66f38b74f6c93f11d82d4da0773.png