求质数算法的 N 种境界[1] - 试除法和初级筛法
Author：zhoulujun Date：
评判笔试答题，【思路和想法】远远比【对错】更重要！
笔试题：
请实现一个函数，对于给定的整型参数 N，该函数能够把自然数中，小于 N 的质数，从小到大打印出来。
比如，当 N = 10，则打印出 2 3 5 7
请实现一个函数，对于给定的整型参数 N，该函数能够从小到大，依次打印出自然数中最小的 N 个质数。
比如，当 N = 10，则打印出2 3 5 7 11 13 17 19 23 29
★试除法
首先要介绍的，当然非“试除法”莫属啦。考虑到有些读者是菜鸟，稍微解释一下。
“试除”，顾名思义，就是不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于 1 的自然数，只要有一个能整除，则 x 是合数；否则，x 是质数。
显然，试除法是最容易想到的思路。不客气地说，也是最平庸的思路。不过捏，这个最平庸的思路，居然也有好多种境界。大伙儿请看：
◇境界1
在试除法中，最最土的做法，就是：
假设要判断 x 是否为质数，就从 2 一直尝试到 x-1。这种做法，其效率应该是最差的。如果这道题目有10分，按照这种方式做出的代码，即便正确无误，俺也只给1分。
◇境界2
稍微聪明一点点的程序猿，会想：x 如果有（除了自身以外的）质因数，那肯定会小于等于 x/2，所以捏，他们就从 2 一直尝试到 x/2 即可。
这一下子就少了一半的工作量哦，但依然是很笨的办法。打分的话，即便代码正确也只有2分。
◇境界3
再稍微聪明一点的程序猿，会想了：除了 2 以外，所有可能的质因数都是奇数。所以，他们就先尝试 2，然后再尝试从 3 开始一直到 x/2 的所有奇数。
这一下子，工作量又少了一半哦。但是，俺不得不说，依然很土。就算代码完全正确也只能得3分。
◇境界4
比前三种程序猿更聪明的，就会发现：其实只要从 2 一直尝试到 √x，就可以了。估计有些网友想不通了，为什么只要到 √x 即可？
简单解释一下：
因数都是【成对】出现滴。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。至于严密的数学证明，用小学数学知识就可以搞定，俺就不啰嗦了。
◇境界5
那么，如果先尝试 2，然后再针对 3 到 √x 的所有【奇数】进行试除，是不是就足够优了捏？答案显然是否定的嘛？写到这里，才刚开始热身哦。
一些更加聪明的程序猿，会发现一个问题：尝试从 3 到 √x 的所有【奇数】，还是有些浪费。
比如：要判断 101 是否质数，101 的根号取整后是 10，那么，按照境界4，需要尝试的奇数分别是：3，5，7，9。但是你发现没有，对 9 的尝试是多余的。不能被 3 整除，必然不能被 9 整除......顺着这个思路走下去，这些程序猿就会发现：其实，只要尝试小于 √x 的【质数】即可。而这些质数，恰好前面已经算出来了（是不是觉得很妙？）。
所以，处于这种境界的程序猿，会把已经算出的质数，先保存起来，然后用于后续的试除，效率就大大提高了。
顺便说一下，这就是算法理论中经常提到的：【以空间换时间】。
◇补充说明
开头的4种境界，基本上是依次递进的。不过捏，境界5跟境界4，是【平级】滴。在俺考察过的应聘者中，有人想到了境界4但没有想到境界5；反之，也有人想到境界5但没想到境界4。通常，这两种境界只要能想到其中之一，俺会给5-7分；如果两种都想到了，俺会给8-10分。
对于俺要招的“初级软件工程师”的岗位，能同时想到境界4和境界5，应该就可以了。如果你对自己要求不高，仅仅满足于浅尝辄止。那么，看到这儿，你就可以打住了，无需再看后续的内容；反之，如果你比较好奇或者希望再多学点东西，请接着往下看...
ChatGPT给的算法
以下是一种用于查找小于给定数n的所有质数的筛选法（Sieve of Eratosthenes）的JavaScript算法：
function findPrimes(n) {
// 创建一个布尔数组，用于标记数是否为质数
let isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
// 从2开始遍历到n的平方根
for (let i = 2; i <= Math.sqrt(n); i++) {
if (isPrime[i]) {
// 将i的倍数标记为非质数
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 收集所有质数到一个数组
let primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push(i);
}
}
return primes;
}
// 示例用法
console.log(findPrimes(4)); // 输出: [2, 3]
console.log(findPrimes(10)); // 输出: [2, 3, 5, 7]该算法使用了筛选法的原理，首先将所有数标记为质数，然后从2开始遍历到n的平方根。对于每个质数i，将其倍数标记为非质数。最后，收集所有标记为质数的数即为小于n的所有质数。
请注意，这个算法的时间复杂度为O(n log log n)，其中n是给定的数。它的效率较高，适用于查找较大范围内的质数。
★筛法
◇何为“筛法”？
说完“试除法”，再来说说筛法（维基百科的解释在“这里”）。俺不妨揣测一下：本文的程序员读者，应该有2/3以上，从来没有听说过筛法。所以捏，顺便跟大伙儿扯扯蛋，聊一下筛法的渊源。
这个筛法啊，真的是一个既巧妙又快速的求质数方法。其发明人是公元前250年左右的一位古希腊大牛——埃拉托斯特尼。为啥说他是大牛捏？因为他本人精通多个学科和领域，至少包括：数学、天文学、地理学（地理学这个词汇，就是他创立的）、历史学、文学（他是一个诗人）。真的堪称“跨领域的大牛”。
他最让俺佩服的是：仅仅用简单的几何方法，测量出了地球的周长、地球与月亮的距离、地球与太阳的距离、赤道与黄道的夹角......而且，这些计算结果跟当代科学家测出的，相差无几。要知道他生活的年代，大概相当于中国的春秋战国。而咱们的老祖宗，一直到明朝还顽固地坚信：天是圆的、地是方的、月亮会被天狗给吃喽......
好了，扯蛋完毕，言归正传。
估计很多人把筛法仅仅看成是一种具体的方法。其实，【筛法还是一种很普适的思想】。在处理很多复杂问题的时候，都可以看到筛法的影子。那么，筛法如何求质数捏，说起来很简单：
首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数......
上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。俺在维基百科上找了一张很形象的动画，能直观地体现出筛法的工作过程。
ChatGPT给的算法
以下是一种用于查找小于给定数n的所有质数的JavaScript算法，称为埃拉托斯特尼筛法（Sieve of Eratosthenes）：
function findPrimes(n) {
// 创建一个布尔数组，用于标记数是否为质数
let isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
// 从2开始遍历到根号n
for (let i = 2; i <= Math.sqrt(n); i++) {
// 如果i是质数，则将i的倍数标记为非质数
if (isPrime[i]) {
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 收集所有质数到一个数组
let primes = [];
for (let i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push(i);
}
}
return primes;
}
// 示例用法
console.log(findPrimes(4)); // 输出: [2, 3]
console.log(findPrimes(10)); // 输出: [2, 3, 5, 7]这个算法利用了埃拉托斯特尼筛法的原理，首先将所有数标记为质数，然后从2开始遍历到根号n，对于每个质数i，将其倍数标记为非质数。最后，收集所有标记为质数的数即为小于n的所有质数。
请注意，这个算法的时间复杂度为O(n log log n)，其中n是给定的数。这是因为在每个质数的倍数上进行标记操作，而不是逐个检查每个数。这使得该算法在查找较大范围内的质数时效率更高。
转载本站文章《求质数算法的 N 种境界[1] - 试除法和初级筛法》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8957.html