Java实现输出100000以内的质（素）数及算法结构优化
2022-04-08 本文已影响0人
羋学僧
输出100000以内的所有质数
质数：也叫素数，只能被1和他本身整除的自然数
最小的质数：2
方法一：效率很低
public class PrimeNumber {
public static void main(String[] args) {
boolean b = true;
//遍历100以内的自然数
for (int i = 2; i <= 100; i++) {
//j：被i除
for (int j = 2; j < i; j++) {
if (i % j == 0) { //%是求模运算，即2%10=2，10%2=0，10%3=1。
b = false;
}
}
if (b) {
System.out.print(i + " ");
}
b = true;
}
}
}
输出结果：
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
实际上，上面的这种方法基本上是效率最低的。但因为100实在是太小了，计算机的运算速度很快就能计算出100以内的质数，所以现在我们不改变算法的结构，把100换成10万试试。
继续方法一：
public class PrimeNumber {
public static void main(String[] args) {
//获取当前时间距离1970-01-01 00:00:00的毫秒数
long start = System.currentTimeMillis();
boolean b = true;
//遍历100以内的自然数
for (int i = 2; i <= 100000; i++) {
//j：被i去除
for (int j = 2; j < i; j++) {
if (i % j == 0) { //%是求模运算，即2%10=2，10%2=0，10%3=1。
b = false;
}
}
if (b) {
System.out.print(i + " ");
}
b = true;
}
//获取当前时间距离1970-01-01 00:00:00的毫秒数
long end = System.currentTimeMillis();
System.out.println("\n花费时间：" + (end - start)); //6243毫秒
}
}
运行结果：
用以上这种方法，输出10万以内的质数居然用了6243毫秒，即6.3秒。在真实开发中。这么慢的速度是绝对不允许的。
所以接下来对这个算法进行优化
方法二：
优化一：使用break更快地跳出循环
public class PrimeNumber {
public static void main(String[] args) {
//获取当前时间距离1970-01-01 00:00:00的毫秒数
long start = System.currentTimeMillis();
//遍历100以内的自然数
for (int i = 2;i<=100000;i++){
boolean b = true;
for (int j=2;j<i;j++){
if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。
b = false;
break;//优化一：只对本身非质数的自然数是有效的
}
}
if (b){
System.out.print(i+" ");
}
}
long end = System.currentTimeMillis();
System.out.println("\n花费时间："+(end-start)); //优化一后：花费时间 619ms
}
}
这一次，我在最内层的if语句中加入了 break;
这样做的目的是让非质数更快的跳出循环，比如for循环到了100，此时i=100，进入第二个for循环，此时j=2，100%2=0，于是马上就break出了循环
运行结果：
可以看到，优化过后的速度立马就上来了，用时615毫秒。
方法三：
既然能对非质数进行优化，那是否可以对质数进行优化呢？当然可以
优化二：对本身是质数的自然数进行优化
public class PrimeNumber {
public static void main(String[] args) {
//获取当前时间距离1970-01-01 00:00:00的毫秒数
long start = System.currentTimeMillis();
//遍历100以内的自然数
for (int i = 2;i<=100000;i++){
boolean b = true;
//优化二：对本身是质数的自然数是有效的
for (int j=2;j<Math.sqrt(i);j++){
if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。
b = false;
}
}
if (b){
System.out.print(i+" ");
}
}
long end = System.currentTimeMillis();
System.out.println("\n花费时间："+(end-start)); //优化二：122ms
}
}
运行结果：
可以看到，现在运行结果相比优化一又快了，用了122ms。
方法四：
最终优化：把优化一和优化二结合。
public class PrimeNumber {
public static void main(String[] args) {
//获取当前时间距离1970-01-01 00:00:00的毫秒数
long start = System.currentTimeMillis();
//遍历100以内的自然数
for (int i = 2;i<=100000;i++){
boolean b = true;
//优化二：对本身是质数的自然数是有效的
for (int j=2;j<Math.sqrt(i);j++){
if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。
b = false;
break;//优化一：只对本身非质数的自然数是有效的
}
}
if (b){
System.out.print(i+" ");
}
}
long end = System.currentTimeMillis();
System.out.println("\n花费时间："+(end-start)); //优化一加优化二：33ms
}
}
运行结果：
两种算法优化结合在一起效果不言而喻，输出10万以内的质数仅用了33毫秒
试除法
int N = 29; //任意选择一个 N，以29为例
int flag = 1; //flag记录 N 的属性。1 代表 N 是质数， 0 则代表不是。我们先默认它是
for(int i = 2;i < N;i++){
if(N % i == 0){ //当 N 除以 i 的余数为 0，说明 N 被 i 整除，即 N 为合数
flag = 0;
break; //因为 N 已经被证明是合数，不需要再继续运算了，跳出循环
}
}
//算法结束，最终 flag 为 1 表示质数，flag 为 0 表示合数。
int N = 29;
int flag = 1;
if(N % 2 == 0) flag = 0; //首先测试 N 是否是偶数
else for(int i = 3;i * i < N;i += 2){ //与刚才不同的是，我们先从 3 开始，每次增加 2，一直
//到根号下 N 为止。这样我们的测试就在奇数中展开
if(N % i == 0){
flag = 0;
break;
}
}
//算法结束，最终 flag 为 1 表示质数，flag 为 0 表示合数。
