方法一：暴力遍历
判断一个数是否为质数最直观的方法就是暴力遍历它的所有可能因子，然后检查是否有除了1和自身以外的因子。对于数字1到100，我们可以使用两层循环来进行遍历。
首先，我们用一个外层循环从2开始遍历每一个数字，这是因为一个数的因子最小为2。然后，我们用一个内层循环从2遍历到这个数字，逐个去判断是否能够整除。若能整除，则说明该数字不是质数，并跳出当前循环。若内层循环能够执行到最后一次，即没有找到任何因子，那么该数字就是质数。
方法二：优化的暴力遍历
在方法一中，我们需要遍历一个数字的所有可能因子，即使我们已经找到了一个因子，后续的遍历仍然会继续执行，这实际上是一种浪费。我们可以对方法一进行一些优化，减少内层循环的遍历范围。
首先，我们仍然用一个外层循环从2开始遍历每一个数字。然而，内层循环的遍历范围可以缩小为从2到这个数字的平方根，即$\sqrt{n}$。这是因为一个数的因子是成对出现的，如果存在一个大于$\sqrt{n}$的因子，那么一定会存在一个小于$\sqrt{n}$的因子。因此，在内层循环中，我们只需要遍历到平方根即可。
方法三：埃氏筛法
除了暴力遍历，还有一种更为高效的质数判断方法，即埃氏筛法。这个方法基于以下观察：
对于一个质数p，p的倍数2p，3p，4p，……都一定不是质数，因此我们可以将它们全部去除。剩下的数字中，最小的数必定是质数，然后再逐步筛除它的倍数，最终得到所有的质数。
具体来说，我们可以用一个bool类型的数组来表示一个数字是否为质数。首先，将所有数字初始化为true，表示它们是质数。然后，从2开始遍历到$n$，对于每一个被判定为质数的数字，将它的所有倍数标记为false。最后，扫描一遍数组，将标记为true的数字输出，即得到了1到100之间的所有质数。
本文来自投稿，不代表亲测学习网立场，如若转载，请注明出处：https://www.qince.net/cyy7o-2.html
郑重声明：
本站所有内容均由互联网收集整理、网友上传，并且以计算机技术研究交流为目的，仅供大家参考、学习，不存在任何商业目的与商业用途。 若您需要商业运营或用于其他商业活动，请您购买正版授权并合法使用。
我们不承担任何技术及版权问题，且不对任何资源负法律责任。
如遇到资源无法下载，请点击这里失效报错。失效报错提交后记得查看你的留言信息，24小时之内反馈信息。
如有侵犯您的版权，请给我们私信，我们会尽快处理，并诚恳的向你道歉！
