极客笔记JavaScript 计算范围内的素数
素数是只有两个完美除数的数字。我们将看到两种方法来找到给定范围内的素数数量。第一种方法是使用蛮力方法，但这种方法的时间复杂度稍高。然后，我们将改进这种方法，并采用更好的时间复杂度的埃拉托色尼筛法。在本文中，我们将使用JavaScript编程语言找到给定范围内的素数总数。
蛮力方法
在这种方法中，首先，我们将学习如何判断一个数字是否为素数，我们可以用两种方法来判断。一种方法是O（N）时间复杂度，另一种方法是O（sqrt（N））时间复杂度。
直接方法：判断一个数字是否为素数
实例
首先，我们将通过一个循环遍历数字，并计算能完全整除该数字的个数，如果能整除该数字的个数不等于2，则该数字不是素数，否则该数字是素数。让我们来看一下代码 –
function isPrime(number){
var count = 0;
for(var i = 1;i<=number;i++) {
if(number%i == 0){
count = count + 1;
}
}
if(count == 2){
return true;
}
else{
return false;
}
}
// checking if 13 and 14 are prime numbers or not
if(isPrime(13)){
console.log("13 is the Prime number");
}
else{
console.log("13 is not a Prime number")
}
if(isPrime(14)){
console.log("14 is the Prime number");
}
else{
console.log("14 is not a Prime number")
}
在上面的代码中，我们从1遍历到number，这是我们可以找到可以整除给定数的数字范围，并得到了可以整除给定数的数字的数量，然后根据此打印结果。
上述代码的时间复杂度为O(N)，检查每个数字是否为素数需要O(N*N)的时间，这意味着这不是一个好的检查方法。
数学方法
我们知道，当一个数能够完全整除另一个数时，商也是一个完全的整数，即如果一个数p能够被数q完全整除且商是r，那么有q * r = p。同时，r也可以完全整除数p并且商是q。因此，这意味着一个完全的约数总是成对出现。
示例
通过上面的讨论，我们可以得出结论，如果我们只检查数的除法直到N的平方根，那么它将在很短的时间内给出相同的结果。让我们看一下上述方法的代码−
function isPrime(number){
if(number == 1) return false
var count = 0;
for(var i = 1;i*i<=number;i++){
if(number%i == 0){
count = count + 2;
}
}
if(count == 2){
return true;
}
else{
return false;
}
}
// checking if 67 and 99 are prime numbers or not
if(isPrime(67)){
console.log("67 is the Prime number");
}
else{
console.log("67 is not a Prime number")
}
if(isPrime(99)){
console.log("99 is the Prime number");
}
else{
console.log("99 is not a Prime number")
}
在上面的代码中，我们只是通过改变for循环的范围来改变之前的代码，现在它只会检查前N个元素的平方根，并且我们将计数增加了2。
上面的代码的时间复杂度是O(sqrt(N))，这是更好的，这意味着我们可以使用这种方法来找到给定范围内的质数数量。
范围L到R内的质数数量
示例
我们将在给定的范围内实施先前给定的代码，并计算给定范围内的质数数量。让我们实施代码-
function isPrime(number){
if(number == 1) return false
var count = 0;
for(var i = 1;i*i<=number;i++) {
if(number%i == 0){
count = count + 2;
}
}
if(count == 2){
return true;
}
else{
return false;
}
}
var L = 10
var R = 5000
var count = 0
for(var i = L; i <= R; i++){
if(isPrime(i)){
count = count + 1;
}
}
console.log(" The number of Prime Numbers in the given Range is: " + count);
在上面的代码中，我们使用for循环从L到R范围遍历，并在每次迭代时检查当前数字是否为素数。如果该数字是素数，则增加计数器，并最后打印该值。
上述代码的时间复杂度为O(N*N)，其中N是范围内的元素数量。
埃拉托斯特尼筛法
示例
埃拉托斯特尼筛法以高效的方式工作，并以O(Nlog(log(N)))的时间在给定范围内找到素数的数量，这与其他算法相比非常快速。筛法所占用的空间为O(N)，但由于时间非常高效，所以不会造成影响。让我们看看代码，然后我们将解释代码-
var L = 10
var R = 5000
var arr = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,1);
arr[0] = 0
arr[1] = 0
for(var i = 2;i<=R;i++){
if(arr[i] == 0){
continue;
}
for(var j = 2; i*j <= R; j++){
arr[i*j] = 0;
}
}
var pre = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,0);
for(var i = 1; i<= R;i++){
pre[i] = pre[i-1] + arr[i];
}
answer = pre[R]-pre[L-1]
console.log("The number of Prime Numbers in the given Range is: " + answer);
在上面的代码中，我们看到了埃拉托斯特尼筛法的实现。首先，我们创建了一个大小为R的包含全部为1的数组，然后我们使用for循环遍历数组，在每次迭代中，如果当前数字不为1则说明不是质数，如果是1则说明是质数，并且我们移除了所有小于R且是当前质数的倍数的数字。然后我们创建了一个前缀数组，用于存储从0到当前索引的质数的个数，并且可以在范围0到R的每个查询中以常数时间提供答案。 时间和空间复杂度 以上给定代码的时间复杂度是 O(N*log(log(N)))，相比于O(N*N)和O(N*sqrt(N))要好得多。以上代码的空间复杂度比之前的代码更大，为O(N)。
结论
在本教程中，我们看到了如何使用JavaScript编程语言找到给定范围内的质数数量。质数是只有两个完美约数的数字。1不是质数，因为它只有一个完美约数。我们介绍了三种方法，时间复杂度分别为O(N*N)、O(N*sqrt(N))和O(N*log(log(N)))。前两种方法的空间复杂度为O(1)，而埃拉托斯特尼筛法的空间复杂度为O(N)。