【算法学习】求得一定数值范围内的所有质数

╰半夏微凉° 2024-04-01 09:36 12阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

## 0. 引子 ##

在面试过程当中，经常会遇到一些算法相关的问题，比如：求100以内的所有质数。

今天我们由这个问题入手，探讨一下算法的用处。

## 1、概念 ##

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

## 2、算法设计 ##

假设要判断的数值为n，只需对除数进行遍历，从2到n-1即可。

import java.util.ArrayList;
    import java.util.List;
    
    public class TestPrime {
    	public static void main(String[] args) {
    		//存储质数
    		List<Integer> primeList = new ArrayList<>();
    		int n = 100;
    		//循环次数
    		int count = 0;
    		for(int i=2;i<=n;i++){
    			//质数标识
    			boolean isPrime = true;
    			for(int j=2;j<=i-1;j++){
    				count++;
    				if(i%j==0){
    					isPrime = false;
    				}
    			}
    			
    			if(isPrime){
    				primeList.add(i);
    			}
    		}
    		//打印质数
    		System.out.println(primeList.toString());
    		//打印循环次数
    		System.out.println(count);
    	}
    }

输出结果为：

> \[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\]  
> 4851

总共循环了4851次。

> 考虑如下三个问题：
> 
> 算法是否正确？
> 
> 算法复杂度如何？
> 
> 算法能否改进？

### 2.1 算法是否正确？ ###

从打印出来结果来看，全是质数，算法结果没有问题。

### 2.2 算法复杂度如何？ ###

> for(int i=2;i<=n;i++)\{ ============》时间复杂度为 n  
> //质数标识  
> boolean isPrime = true;  
> for(int j=2;j<=i-1;j++)\{ ============》时间复杂度为 n/2  
> count++;  
> if(i%j==0)\{  
> isPrime = false;  
> \}  
> \}

整体复杂度为n^2/2

### 2.3 算法能否改进？ ###

能，在判断非质数条件成立时，可以使用 break 语句终止当前循环。

## 3、算法优化一 ##

当前数值为非质数时，即结束当前层的for循环，提高执行效率。

import java.util.ArrayList;
    import java.util.List;
    
    public class TestPrime {
    	public static void main(String[] args) {
    		//存储质数
    		List<Integer> primeList = new ArrayList<>();
    		int n = 100;
    		//循环次数
    		int count = 0;
    		for(int i=2;i<=n;i++){
    			//质数标识
    			boolean isPrime = true;
    			for(int j=2;j<=i-1;j++){
    				count++;
    				if(i%j==0){
    					isPrime = false;
    					break;
    				}
    			}
    			
    			if(isPrime){
    				primeList.add(i);
    			}
    		}
    		//打印质数
    		System.out.println(primeList.toString());
    		//打印循环次数
    		System.out.println(count);
    	}
    }

输出结果如下：

> \[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\]  
> 1133

总共循环了1133次，是上一次结果的四分之一，虽然效率有所提升，但效果并不明显，没有实现量级跃升。

还能再继续优化吗？

## 4、算法优化二 ##

之前的计算中，除数是循环到了n-1，其实并没有必要，因为当除数达到n/2时，就已经到了整除n的极限了，当除数超过 n/2 + 1时，无论如何也不能将n整除了。

优化后如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class TestPrime {
    	public static void main(String[] args) {
    		//存储质数
    		List<Integer> primeList = new ArrayList<>();
    		int n = 100;
    		//循环次数
    		int count = 0;
    		for(int i=2;i<=n;i++){
    			//质数标识
    			boolean isPrime = true;
    			for(int j=2;j<=i/2;j++){
    				count++;
    				if(i%j==0){
    					isPrime = false;
    					break;
    				}
    			}
    			
    			if(isPrime){
    				primeList.add(i);
    			}
    		}
    		//打印质数
    		System.out.println(primeList.toString());
    		//打印循环次数
    		System.out.println(count);
    	}
    }

运行结果如下：

> \[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\]  
> 616

总共循环了616次，这次可以发现，执行次数较之前大幅提升了一个数量级。

还能再优化吗？

## 5、算法优化三 ##

沿着4中的思路，继续分析，当除数达到n/2时，其实已经在除数为2时得到了验证，故这里已经出现了重复。

该问题的计算思路，可以转换为：计算数值n下的所有约数中，除了1和自身外，是否还存在其它数值，如果没有，就是质数。当 x^2 = n 即为约数集中最中间的数值，其它约数都分布在x的两边。

算法优化如下：

import java.util.ArrayList;
    import java.util.List;
    
    public class TestPrime {
    	public static void main(String[] args) {
    		//存储质数
    		List<Integer> primeList = new ArrayList<>();
    		int n = 100;
    		//循环次数
    		int count = 0;
    		for(int i=2;i<=n;i++){
    			//质数标识
    			boolean isPrime = true;
    			for(int j=2;j<=Math.sqrt(i+1);j++){
    				count++;
    				if(i%j==0){
    					isPrime = false;
    					break;
    				}
    			}
    			
    			if(isPrime){
    				primeList.add(i);
    			}
    		}
    		//打印质数
    		System.out.println(primeList.toString());
    		//打印循环次数
    		System.out.println(count);
    	}
    }

输出如下：

> \[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\]  
> 237

总共循环了237次。

大家再看看，对于该算法，还有什么可以优化的空间么？

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16