java输出1~100之间的全部素数的5种方法

2024-01-16 09:28| 来源: 网络整理| 查看: 265

文章目录一、前言二、需求分析2.1 . 什么是素数?2.2 分析三、代码实现3.1 方法一：根据素数的定义来遍历检查3.2 方法二：根据判断条件2进行遍历检查，减少遍历次数3.3 方法三：根据判断条件3进行遍历检查，减少遍历次数3.4 方法四：在方法三的前提上优化，优化基础是除2外的所有偶数均不是素数3.5 方案五：优化更长的素数计算四、完整的代码实现

一、前言

在我们面试或者初学java 会遇到请用java输出1~100的所有素数，这样一道问题，这道题有很多的解法，接下来我们将讲解其中的 5种方案:

二、需求分析 2.1 . 什么是素数?

经查询小学二年级的数学课本可知：

只能被1和本身整除的称为素数 2.2 分析

判断是不是素数的方法很多，但不外乎是循环嵌套外加条件语句；故我们可以分析出以下判断条件：

判断条件1：只能被1和本身整除的称为素数；判断条件2：在区间（1，x/2）中找不到能整除素数x的整数；判断条件3：在区间（1，sqrt(x)）中找不到能整除素数x的整数；三、代码实现 3.1 方法一：根据素数的定义来遍历检查

这种方案也是最简单，最容易想到的方法。

/** * 方法一：根据素数的定义来遍历检查 */ private static void method1() { //外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) for (int i = 2; i //判断是否存在j能整除i，若存在，则更改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } 3.2 方法二：根据判断条件2进行遍历检查，减少遍历次数 /** * 方法二：根据判断条件2进行遍历检查，减少遍历次数 * 外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) */ private static void method2() { for (int i = 2; i //判断是否存在除数j能整除i，若存在，则修改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } 3.3 方法三：根据判断条件3进行遍历检查，减少遍历次数 /** * 方法三：根据判断条件3进行遍历检查，减少遍历次数 * 外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) */ private static void method3() { for (int i = 2; i //判断是否存在除数j能整除i，若存在，则修改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } 3.4 方法四：在方法三的前提上优化，优化基础是除2外的所有偶数均不是素数 /**方法四：在方法三的前提上优化，优化基础是除2外的所有偶数均不是素数， *(i+=2)只遍历奇数，减少外层遍历次数；同理，由于奇数是不能被偶数整除的， *(j+=2)只遍历奇数，减少内层遍历次数 */ private static void method4() { System.out.print("2 "); //外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) for (int i = 3; i //判断是否存在除数j能整除i，若存在，则修改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } 3.5 方案五：优化更长的素数计算

联想一下，能被2整除（偶数）的直接剔除，同样的道理，能被3or5整除的剔除掉会不会让外层循环的次数更少呢？此处才到100，若是1000呢？10000呢？定义一个数组，由于剔除了偶数，故数组长度不会超过总个数的一半。

/** * 联想一下，能被2整除（偶数）的直接剔除，同样的道理，能被3or5整除的剔除掉会不会让外层循环的次数更少呢？ * 此处才到100，若是1000呢？10000呢？ * 定义一个数组，由于剔除了偶数，故数组长度不会超过总个数的一半 */ private static void method5() { int[] arr = new int[500]; int count = 0; for (int i = 6; i flag = false; } if (flag) { arr[count] = i; count++; } } System.out.println("6~1000中剔除能被2or3or5整除的数后还剩" + count + "个"); System.out.println("1~1000中所有素数为："); System.out.print("2" + "\t"); System.out.print("3" + "\t"); System.out.print("5" + "\t"); count = 0; for (int i = 0; i break; } for (int j = 7; j flag = false; break; } } if (flag) { System.out.print((arr[i]) + "\t"); count++; } } System.out.println("\n" + "---------------------"); System.out.println("\n" + "其中6~1000中剔除能被2or3or5整除的数中还是素数的有" + count + "个"); } 四、完整的代码实现 package com.ratel.skywalking.order; /* 分析： 1.素数：判断条件1：只能被1和本身整除的称为素数；判断条件2：在区间（1，x/2）中找不到能整除素数x的整数；判断条件3：在区间（1，sqrt(x)）中找不到能整除素数x的整数； 2.方法：很多，但不外是循环嵌套外加条件语句； */ class PrintSuShu { public static void main(String[] args) { method1(); method2(); method3(); method4(); method5(); } /** * 联想一下，能被2整除（偶数）的直接剔除，同样的道理，能被3or5整除的剔除掉会不会让外层循环的次数更少呢？ * 此处才到100，若是1000呢？10000呢？ * 定义一个数组，由于剔除了偶数，故数组长度不会超过总个数的一半 */ private static void method5() { int[] arr = new int[500]; int count = 0; for (int i = 6; i flag = false; } if (flag) { arr[count] = i; count++; } } System.out.println("6~1000中剔除能被2or3or5整除的数后还剩" + count + "个"); System.out.println("1~1000中所有素数为："); System.out.print("2" + "\t"); System.out.print("3" + "\t"); System.out.print("5" + "\t"); count = 0; for (int i = 0; i break; } for (int j = 7; j flag = false; break; } } if (flag) { System.out.print((arr[i]) + "\t"); count++; } } System.out.println("\n" + "---------------------"); System.out.println("\n" + "其中6~1000中剔除能被2or3or5整除的数中还是素数的有" + count + "个"); } /**方法四：在方法三的前提上优化，优化基础是除2外的所有偶数均不是素数， *(i+=2)只遍历奇数，减少外层遍历次数；同理，由于奇数是不能被偶数整除的， *(j+=2)只遍历奇数，减少内层遍历次数 */ private static void method4() { System.out.print("2 "); //外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) for (int i = 3; i //判断是否存在除数j能整除i，若存在，则修改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } /** * 方法三：根据判断条件3进行遍历检查，减少遍历次数 * 外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) */ private static void method3() { for (int i = 2; i //判断是否存在除数j能整除i，若存在，则修改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } /** * 方法二：根据判断条件2进行遍历检查，减少遍历次数 * 外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) */ private static void method2() { for (int i = 2; i //判断是否存在除数j能整除i，若存在，则修改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } /** * 方法一：根据素数的定义来遍历检查 */ private static void method1() { //外层循环遍历被除数i(因为1既不是素数也不是和数，所以直接从2开始遍历) for (int i = 2; i //判断是否存在j能整除i，若存在，则更改flag的值并跳出循环 if (0 == i % j) { flag = false; break; } } //根据flag的值判断是否输出i if (flag) { System.out.print(i + " "); } } System.out.println('\n' + "---------------------------"); } }

【本文地址】

公司简介

联系我们