JAVA筑基100例第2题判断101200之间有多少个素数

　　作者简介：大家好,我是小虚竹。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 + ＂是素数＂);             }         }     } }
　　解法二：循环对半法思路
　　素数，又称质数，定义是：除了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 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 primes(int startNum,int endNum){         List 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 + ＂是素数＂);                 }              }         } }
　　我是虚竹哥，我们下一题见