零、前言
今天是学习 「JAVA语言」 打卡的第2天，我的学习策略很简单，题海策略+ 费曼学习法。如果能把这100题都认认真真自己实现一遍，那意味着 「JAVA语言」 已经筑基成功了。后面的进阶学习，可以继续跟着我，一起走向架构师之路。
一、题目描述
题目：判断 101-200 之间有多少个素数，并输出所有素数。
二、解题思路：循环法
素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。
判断素数的方法：从2到n-1判断有没有能整除n的数。如果有，则不是素数，否则，是素数
三、代码详解
public class Basics02 {
public static void main(String[] args) {
int i, j;
// 从101～200进行筛选
for (i = 101; i <= 200; i++)
{
// 从2～i-1的值
for (j = 2; j <= i - 1; j++) {
if (i % j == 0){
// i与j互相取余，如果余数为0则肯定不是素数，跳出循环
break;
}
}
if (i == j) {
// 如果i等于j则说明完成了从2～i-1的循环，说明每一次取余的值都不是0。结果肯定是素数
System.out.println(i + "是素数");
}
}
}
}
解法二：循环对半法
思路
素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。 从2到n-1判断有没有能整除n的数。每拿到一个数，判断该数是否是素数；
从2开始，遍历到该数的一半的数据，看是否有数据可以整除它，有就不是素数，没有就是素数。
注：为什么是该数的一半，因为素数的特性，那肯定不能被2整除了，被2后面的数整除得到的数据肯定小于该数的一半。
这种写法会少循环一半的数据。提高效率。
代码详解
public class Basics02_2 {
public static void main(String[] args) {
int i, j;
// 从101～200进行筛选
for (i = 101; i <= 200; i++)
{
//标记位 //当前的数是素数
boolean flag = true;
// 从2～i-1的值
for (j = 2; j <= i /2; j++) {
if (i % j == 0){
// i与j互相取余，如果余数为0则肯定不是素数，跳出循环
flag = false;
break;
}
}
if (flag) {
// 根据标记位flag的结果。true结果肯定是素数
System.out.println(i + "是素数");
}
}
}
}
解法三：开方法
思路
素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。 开方求解 原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行。 证明： 假设数m=p*q,且p≤q 则m≥p*p 所以p<= √m
由此可得出上面的结论，一个数如果存在约数，那肯定一个约数在其开方的左边，另一个约数在其开方的右边。
代码详解
public class Basics02_3 {
public static void main(String[] args) {
// 从101～200进行筛选
for (int i = 101; i <= 200; i++) {
// 开方 求解 原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行
int sqrtNum = (int)Math.sqrt(i);
for (int k = 2; k <= sqrtNum; k++) {
if (i % k == 0){
// i与k互相取余，如果余数为0则肯定不是素数，跳出循环
break;
}
//执行到这里，说明这个数在其开方的左边找不到约数
if(k>= sqrtNum){
System.out.println(i + "是素数");
}
}
}
}
}
解法四：试除法升级版
思路
其实前面几种都是试除法，那虚竹哥就简单介绍下试除法的概念： “试除”，顾名思义，就是不断地尝试能否整除。比如要判断自然数 x 是否素数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是 合数 ；否则，x 是素数。
素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。 开方求解 原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行。 质因数 ，是指能整除给定正整数的质数。指一个正整数的约数，并且该数还属于是质数的数字。 判断素数，真的需要拿2~ 间的所有整数去除吗？这样有些浪费，比如要判断101是否质数，101的 根号 取整后是10，需要尝试的数分别是：3，4，5，6，7，8，9，10的数。 明显我们知道，除了2之外，所有的可能的质因数，都是奇数。那再优化下，就是需要尝试的数分别是：3，5，7，9的数。其中9肯定不行。那就是3，5，7。。 重点来了，有没有发现什么，都是素数啊。 结论：只要尝试试除小于的素数即可。 代码实现步骤：
- 从101～200进行筛选 循环 只要尝试小于√x 的素数即可其中获取√x 的素数抽象出一个方法出来其中要用到算法理论的： 「以空间换时间。」
代码详解
public class Basics02_4 {
public static void main(String[] args) {
//从101～200进行筛选 循环
//只要尝试小于√x 的质数即可
//获取√x 的质数
for (int i = 101; i <= 200; i++) {
//√x的值
int sqrtNum = (int)Math.sqrt(i);
//只要尝试小于√x 的质数即可
//√x 的质数的获取
List<Integer> primeList = primes(2,sqrtNum);
boolean flag = true;
for (int j = 0; j < primeList.size(); j++) {
if (i % primeList.get(j) == 0){
// i与k互相取余，如果余数为0则肯定不是素数，跳出循环
flag = false;
break;
}
}
if(flag){
System.out.println(i + "是素数");
}
}
}
private static List<Integer> primes(int startNum,int endNum){
List<Integer> primeList = new ArrayList<>();
primeList.add(2);
primeList.add(3);
for (int i = startNum; i <= endNum; i++) {
//开方求解 原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行
int sqrtNum = (int)Math.sqrt(i);
for (int k = 2; k <= sqrtNum; k++) {
if (i % k == 0){
// i与k互相取余，如果余数为0则肯定不是素数，跳出循环
break;
}
//执行到这里，说明这个数在其开方的左边找不到约数
if(k>= sqrtNum){
primeList.add(i);
}
}
}
return primeList;
}
}
解法五：素数筛
思路
素数的倍数不是素数.
代码详解
public class Basics02_5 {
public static void main(String[] args) {
//定义vis数组 true： 表示不是素数 false：表示是素数
boolean[] vis = new boolean[201];//默认初始值为false，即默认全为素数
vis[0] = vis[1] = true; //0,1 不是素数
for (int i = 2; i <= 200; i++) {
//素数的倍数一定不是素数
for (int j = i*i; j <= 200; j += i) {
vis[j] = true;
}
}
for (int i = 0; i <= 200; i++) {
if (!vis[i] && i>101){
System.out.println(i + "是素数");
}
}
}
}
我是虚竹哥，我们下一题见～
