快捷搜索:  汽车  科技

java计算1-100间自然数之和(JAVA筑基100例第2题判断)

java计算1-100间自然数之和(JAVA筑基100例第2题判断)判断素数的方法:从2到n-1判断有没有能整除n的数。如果有,则不是素数,否则,是素数素数,又称质数,定义是:除了1和它本身以外不再有其他的除数整除。❞今天是学习 「JAVA语言」 打卡的第2天,我的学习策略很简单,题海策略 费曼学习法。如果能把这100题都认认真真自己实现一遍,那意味着 「JAVA语言」 已经筑基成功了。后面的进阶学习,可以继续跟着我,一起走向架构师之路。题目:判断 101-200 之间有多少个素数,并输出所有素数。

❤️作者简介:大家好 我是小虚竹。Java领域优质创作者,CSDN博客专家,华为云享专家,掘金年度人气作者,阿里云专家博主,51CTO专家博主

❤️技术活,该赏

❤️点赞 收藏 ⭐再看,养成习惯

零、前言

今天是学习 「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 "是素数"); } } } }

java计算1-100间自然数之和(JAVA筑基100例第2题判断)(1)

解法二:循环对半法思路

素数,又称质数,定义是:除了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 "是素数"); } } } }

java计算1-100间自然数之和(JAVA筑基100例第2题判断)(2)

解法三:开方法思路

素数,又称质数,定义是:除了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 "是素数"); } } } } }

java计算1-100间自然数之和(JAVA筑基100例第2题判断)(3)

解法四:试除法升级版思路

其实前面几种都是试除法,那虚竹哥就简单介绍下试除法的概念: "试除",顾名思义,就是不断地尝试能否整除。比如要判断自然数 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; } }

java计算1-100间自然数之和(JAVA筑基100例第2题判断)(4)

解法五:素数筛思路

素数的倍数不是素数.

代码详解

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 "是素数"); } } } }

java计算1-100间自然数之和(JAVA筑基100例第2题判断)(5)

我是虚竹哥,我们下一题见~

猜您喜欢: