JAVA取质数（素数）算法优化

2024-07-11 15:33| 来源: 网络整理| 查看: 265

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。也可以理解为：这个数与除1之外小于它的数取余不为0，则这个数为质数。

案例

我们在学习或者面试过程中经常会问：输出100以内的所有质数

那我们简单整理一下思路： 1. 定义整型变量，i 和 j 2. 利用for循环的嵌套一个一个判断是否i能否被j整除（i % j == 0） 3. 如果能被整除，也就是说 i 不是质数 4. 定义一个标识，（ isFlag = true），如果这个标识没有被改变，这个数就是质数 5. 输出这个数，然后通过外循环进行判断下一个 i 是不是质数代码如下： public static void main(String[] args) { boolean isFlag = true; for (int i = 2; i if (i % j == 0) { isFlag = false; } } if (isFlag) { System.out.println(i); } isFlag = true; } }

【拓展】这种方法对于查找100以内的质数来说还是可以的，但是如果将100改成100000呢？或者更大的数呢？那么这种方式还是否同样好用呢？于是我做了如下尝试，将100改成10000，并在代码中添加时间计数器，看最后程序运行完毕需要的时间是多少。 demo1:

public static void main(String[] args) { boolean isFlag = true; long start = System.currentTimeMillis();//获取系统当前累计毫秒数 for (int i = 2; i if (i % j == 0) { isFlag = false; } } if (isFlag) { System.out.println(i); } isFlag = true; } long end = System.currentTimeMillis();//获取系统当前累计毫秒数 System.out.println("所花费的时间为" + (end - start) + "毫秒"); }

所花费的时间为13919毫秒。 (可以看到，运行效率就低了很多，当然代码运行效率与硬件也有关)

那我们该如何优化呢？

优化一

可以在if条件里面增加break，当能被整除，则不用继续循环下去了，代码如下：

public static void main(String[] args) { boolean isFlag = true; long start = System.currentTimeMillis();//获取系统当前累计毫秒数 for (int i = 2; i if (i % j == 0) { isFlag = false; break; // 优化一：满足条件跳出循环。只对本身非质数的自然数是有效的 } } if (isFlag) { System.out.println(i); } isFlag = true; } long end = System.currentTimeMillis();//获取系统当前累计毫秒数 System.out.println("所花费的时间为" + (end - start) + "毫秒"); }

所花费的时间为1136毫秒,这个时候就可以看到运行效率快了很多，但这还不是最优解法，可以看一下优化二。

优化二

上面我们使用break优化，满足了对本身非质数的自然数的优化，那是不是可以对本身是质数的在做一次优化呢，我们可以使用 Math.sqrt(i) 代码示例：

所花费的时间为53毫秒。这就明显快了很多了

我们也可以做一下其他的优化，如 System.out.println(i) 也是比较消耗性能的，可以将代码注释,替换成累加count:

public static void main(String[] args) { boolean isFlag = true; int count = 0; long start = System.currentTimeMillis();//获取系统当前累计毫秒数 for (int i = 2; i if (i % j == 0) { isFlag = false; break; // 优化一：满足条件跳出循环。只对本身非质数的自然数是有效的 } } if (isFlag) { count++; // System.out.println(i); } isFlag = true; } long end = System.currentTimeMillis();//获取系统当前累计毫秒数 System.out.println("100000以内的质数个数为" + count + "个"); System.out.println("所花费的时间为" + (end - start) + "毫秒"); }

100000以内的质数个数为9592个所花费的时间为12毫秒

这个时候赶脚自己还要学习的很多呀！！！

【本文地址】

公司简介

联系我们