零、前言
今天是学习 「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 + "是素数");
}
}
}
}
我是虚竹哥,我们下一题见~