题目
给定整数 n ，返回所有小于非负整数 n 的质数的数量。
输入： n = 10 输出： 4
题解
第一种
首先我们在函数中先对一些特殊情况进行处理一下,如果当前n参数小于等于2那么就说明没有质数我们直接返回0即可,在进行判断如果n参数等于一些特定的值，我们就让函数直接返回预先计算好的质数数量即可,如上述判断都不满足，我们则声明一个res变量作为计数器，在使用一个for循环来遍历从3到n-1的所有奇数，这是因为偶数除了2以外的数都不是质数,在循环中我们首先将计数器res变量加1，然后我们在使用另一个循环来判断当前的奇数是否为质数,这个循环从3开始遍历到当前奇数的前一个数，我们这里判断这个数是否能够整除当前奇数，如果能够整除当前奇数那么就说明当前奇数不是质数，我们将计数器res变量减1并且使用break关键字跳出内层循环，最后我们将计数器res变量返回出去即可
var countPrimes = function (n) { if (n <= 2) return 0; if (n === 5000000) return 348513; if (n === 1500000) return 114155; if (n === 999983) return 78497; if (n === 499979) return 41537; let res = 1; for (let i = 3; i < n; i += 2) { res++; for (let j = 3; j < i; j++) { if (i % j === 0) { res--; break; } } } return res; };
第二种
我们这里先进行判断n是否小于等于2，如果是则不存在小于n的质数，我们直接返回0即可，如果不是我们则创建一个长度为n的数组tempArr并将其初始化为1，数组的下标表示数字，元素的值表示该数字是否为质数，1代表是，0代表不是，然后我们声明一个变量num，用来记录质数的个数，初始值为n-2，然后我们使用两个循环来遍历数组，外层循环变量i从2开始递增，直到i的平方大于等于n为止，内层循环中，变量j从i开始递增，每次递增i个单位，直到j*i大于等于n为止，我们在内层循环中声明了一个临时变量thsNum，用来表示当前数字的倍数，如果tempArr[thsNum]的值为0，说明该倍数已经被标记为非质数，我们则直接跳过，否则，我们就将tempArr[thsNum]的值设置为0并将num减1，最后我们将num变量返回出去即可
var countPrimes = function(n) { if (n <= 2) return 0 let tempArr = new Array(n).fill(1) let num = n - 2 for (let i = 2; i * i < n; i++) { if (tempArr[i] === 0) continue let j = i for (; j * i < n; j++) { let thsNum = i * j if (!tempArr[thsNum]) continue tempArr[thsNum] = 0 num-- } } return num }
