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

　　作者简介：大家好，我是小虚竹。Java领域优质创作者，CSDN博客专家，华为云享专家，掘金年度人气作者，阿里云专家博主，51CTO专家博主
　　技术活，该赏
　　点赞收藏再看，养成习惯
　　零、前言
　　今天是学习JAVA语言打卡的第2天，我的学习策略很简单，题海策略费曼学习法。如果能把这100题都认认真真自己实现一遍，那意味着JAVA语言已经筑基成功了。后面的进阶学习，可以继续跟着我，一起走向架构师之路。一、题目描述
　　题目：判断101200之间有多少个素数，并输出所有素数。二、解题思路：循环法
　　素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。
　　判断素数的方法：从2到n1判断有没有能整除n的数。如果有，则不是素数，否则，是素数三、代码详解publicclassBasics02｛publicstaticvoidmain（String〔〕args）｛inti，j；从101～200进行筛选for（i101；i200；i）｛从2～i1的值for（j2；ji1；j）｛if（ij0）｛i与j互相取余，如果余数为0则肯定不是素数，跳出循环break；｝｝if（ij）｛如果i等于j则说明完成了从2～i1的循环，说明每一次取余的值都不是0。结果肯定是素数System。out。println（i是素数）；｝｝｝｝
　　解法二：循环对半法思路
　　素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。从2到n1判断有没有能整除n的数。每拿到一个数，判断该数是否是素数；
　　从2开始，遍历到该数的一半的数据，看是否有数据可以整除它，有就不是素数，没有就是素数。
　　注：为什么是该数的一半，因为素数的特性，那肯定不能被2整除了，被2后面的数整除得到的数据肯定小于该数的一半。
　　这种写法会少循环一半的数据。提高效率。代码详解publicclassBasics022｛publicstaticvoidmain（String〔〕args）｛inti，j；从101～200进行筛选for（i101；i200；i）｛标记位当前的数是素数booleanflagtrue；从2～i1的值for（j2；ji2；j）｛if（ij0）｛i与j互相取余，如果余数为0则肯定不是素数，跳出循环flagfalse；break；｝｝if（flag）｛根据标记位flag的结果。true结果肯定是素数System。out。println（i是素数）；｝｝｝｝
　　解法三：开方法思路
　　素数，又称质数，定义是：除了1和它本身以外不再有其他的除数整除。开方求解原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行。证明：假设数mpq，且pq则mpp所以pm
　　由此可得出上面的结论，一个数如果存在约数，那肯定一个约数在其开方的左边，另一个约数在其开方的右边。代码详解publicclassBasics023｛publicstaticvoidmain（String〔〕args）｛从101～200进行筛选for（inti101；i200；i）｛开方求解原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行intsqrtNum（int）Math。sqrt（i）；for（intk2；ksqrtNum；k）｛if（ik0）｛i与k互相取余，如果余数为0则肯定不是素数，跳出循环break；｝执行到这里，说明这个数在其开方的左边找不到约数if（ksqrtNum）｛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的素数抽象出一个方法出来其中要用到算法理论的：以空间换时间。代码详解publicclassBasics024｛publicstaticvoidmain（String〔〕args）｛从101～200进行筛选循环只要尝试小于x的质数即可获取x的质数for（inti101；i200；i）｛x的值intsqrtNum（int）Math。sqrt（i）；只要尝试小于x的质数即可x的质数的获取ListIntegerprimeListprimes（2，sqrtNum）；booleanflagtrue；for（intj0；jprimeList。size（）；j）｛if（iprimeList。get（j）0）｛i与k互相取余，如果余数为0则肯定不是素数，跳出循环flagfalse；break；｝｝if（flag）｛System。out。println（i是素数）；｝｝｝privatestaticListIntegerprimes（intstartNum，intendNum）｛ListIntegerprimeListnewArrayList（）；primeList。add（2）；primeList。add（3）；for（intistartNum；iendNum；i）｛开方求解原理：一个数的约数在其开方的左边，那肯定会存在一个约数在其开方的右边，所以只要循环到开方数就行intsqrtNum（int）Math。sqrt（i）；for（intk2；ksqrtNum；k）｛if（ik0）｛i与k互相取余，如果余数为0则肯定不是素数，跳出循环break；｝执行到这里，说明这个数在其开方的左边找不到约数if（ksqrtNum）｛primeList。add（i）；｝｝｝returnprimeList；｝｝
　　解法五：素数筛思路
　　素数的倍数不是素数。代码详解publicclassBasics025｛publicstaticvoidmain（String〔〕args）｛定义vis数组true：表示不是素数false：表示是素数boolean〔〕visnewboolean〔201〕；默认初始值为false，即默认全为素数vis〔0〕vis〔1〕true；0，1不是素数for（inti2；i200；i）｛素数的倍数一定不是素数for（intjii；j200；ji）｛vis〔j〕true；｝｝for（inti0；i200；i）｛if（！vis〔i〕i101）｛System。out。println（i是素数）；｝｝｝｝
　　我是虚竹哥，我们下一题见～