0. 引子
在面试中，经常会遇到一些算法相关的问题，比如：求100以内的所有质数。
今天我们由这个问题入手，探讨一下算法的用处。
1、概念
质数（prime number）又称素数，有无限个。质数定义为：在大于1的自然数中，除了1和它本身以外不再有其他因数。
2、算法设计
假设要判断的数值为n，只需对除数进行遍历，从2到n-1即可。
比如我们要求得100以内的所有质数。
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 count++; if(i%j==0){ isPrime = false; } }复制代码
整体复杂度为 n^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的两边。
比如9的约数为3，我们只要循环到3即可判断该数值是否能被除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<=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次。
大家再看看，对于该算法，还有什么可以优化的空间么？
作者：头发尚在链接：https://juejin.cn/post/7195938271306858554/来源：稀土掘金著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。