Java经典案例之用三种方法求1~100以内素数之和

2024-02-18 06:10| 来源: 网络整理| 查看: 265

素数，不能被除了1和本身以外整除的数被称为素数。接下来我用三种方式求得1~100以内素数。

方式一

外层每循环一次，内层就计算出这个数有几个因子，我们都知道素数的因子只有两个，所以如果个数为2就加进总和里面：

package day_11_25; /** * 计算1-100之间的素数和 * * @author soberw */ public class PrimeFor { public static void main(String[] args) { //记录和 int sum = 0; //记录因子个数 int count = 0; int counter = 0; for (int i = 2; i counter++; if (i % j == 0) { count++; } } //两个因子为素数 if (count == 2) { sum += i; } } System.out.println("总和为" + sum); System.out.println("循环了" + counter + "次"); } }

运行结果：在这里插入图片描述共计算了5049次。

方式二

方式一虽然好理解，但是也存在很多的问题，比如如果一个数他本来就是偶数（当然除了2）,那就没有判断的必要了，也还有就是没有中断条件，就算已经知道了这个数不是素数了，但程序还是从头到尾循环了一遍，于是我做了改进，加入了互斥锁，并且从2开始计算（因为最小素数为2），实现如下：

package day_11_25; /** * 计算1-100之间的素数和 * * @author soberw */ public class PrimeFor2 { public static void main(String[] args) { int sum = 0; //声明互斥锁 boolean flag = true; int counter = 0; for (int i = 2; i continue; } //从2到除了它本身的数之间判断 for (int j = 2; j flag = false; break; } } if (flag) { sum += i; } } System.out.println("总和为" + sum); System.out.println("循环了" + counter + "次"); } }

运行结果：在这里插入图片描述

相比于第一种方法确实快了不少，共计算了1084次。

方式三

那么有没有更好的方法呢，答案是肯定的，我们在判断的时候，都是从头到尾去循环一遍，就算是加了互斥锁，也要一次加一个去判断，有点繁琐。那有没有更好的解决方式呢，于是我就想到了下面这种方法，通过开平方判断。打个比方，如果我们要判断100是不是素数，就首先确定一个中间数，你可以找到100的根（10），将数分成两份，如图：在这里插入图片描述图可能画的有点抽象，其实就是我们将10作为中间数，10前面的数乘以10后面的数如果有出现等于100的情况，那就不是素数（比如2x50=100）。因为因子都是成对存在的，1和100，2和50，4和25，5和20，10和10。成对的因子，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。所以这样一来我们就最多判断10次就行了，一下子减少了90次。效率成倍提高。而且实现起来也不复杂，如下：

package day_11_25; /** * 计算1-100之间的素数和 * * @author soberw */ public class PrimeFor3 { public static void main(String[] args) { int sum = 0; int counter = 0; label: for (int i = 2; i continue; } for (int j = 2; j continue label; } } sum += i; } System.out.println(sum); System.out.println(counter); } }

运行结果：在这里插入图片描述仅仅计算了187次，相比于前两种方法，大大的提高了效率。

【本文地址】

公司简介

联系我们