JavaScript program for counting prime numbers in a range

A prime number is a number that has exactly two perfect divisors. We'll see two ways to find the number of prime numbers in a given range. The first is to use a brute force method, which has a somewhat high time complexity. We will then improve this method and adopt the Sieve of Eratosthenes algorithm to have better time complexity. In this article, we will find the total number of prime numbers in a given range using JavaScript programming language.

violence law

First, in this method, we will learn how to find whether a number is prime or not, we can find it in two ways. One method has time complexity O(N) and the other method has time complexity O(sqrt(N)).

Direct method to determine whether a number is prime

Example

First, we will perform a for loop until we get a number, and count the numbers that can divide the number. If the number that can divide the number is not equal to 2, then the number is not a prime number, otherwise number is a prime number. Let's look at the code -

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")
}

In the above code, we traverse from 1 to number, find the number in the number range that can divide the given number, and get how many numbers can divide the given number, and print the result based on this.

The time complexity of the above code is O(N), checking whether each number is prime will cost O(N*N), which means this is not a good way to check.

mathematical method

We know that when one number completely divides another number, the quotient is also a perfect integer, that is, if a number p can be divided by a number q, the quotient is r, that is, q * r = p. r also divides the number p by the quotient q. So this means that perfect divisors always come in pairs.

Example

From the above discussion, we can conclude that if we only check the division to the square root of N, then it will give the same result in a very short time. Let’s see the code of the above method -

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")
}

In the above code, we have just changed the previous code by changing the scope of the for loop, because now it will only check the first square root of N elements, and we have increased the count by 2.

The time complexity of the above code is O(sqrt(N)), which is better, which means that we can use this method to find the number of prime numbers that exist in a given range.

The number of prime numbers in the range from L to R

Example

We will implement the code given before in a range and count the number of prime numbers in a given range. Let's implement the code -

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);

In the above code, we iterate over the range from L to R using a for loop, and on each iteration, we check if the current number is a prime number. If the number is prime, then we increment the count and finally print the value.

The time complexity of the above code is O(N*N), where N is the number of elements in Range.

Eratosthenes algorithm screening

Example

The Sieve of Eratosthenes algorithm is very efficient and can find the number of prime numbers within a given range in O(Nlog(log(N))) time. Compared with other algorithms, it is very fast. . The sieve takes up O(N) space, but that doesn't matter because the time is very efficient. Let's look at the code and then we'll move on to the explanation of the code -

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);

In the above code, we see the implementation of the Sieve of Eratosthenes. First we created an array containing size R and after that we iterated through the array using for loop and for each iteration if the current number is not 1 it means it is not prime otherwise it is prime and we have All numbers less than R that are multiples of the current prime are removed. We then create a prefix array that will store the prime count from 0 to the current index and can provide an answer to every query in the range 0 to R in constant time.

Time and space complexity

The time complexity of the above code is O(N*log(log(N))), which is much better compared to O(N*N) and O(N*(sqrt(N))). Compared to the previous code, the above code has a higher space complexity of O(N).

in conclusion

In this tutorial, we learned how to find the number of prime numbers in a given range using JavaScript programming language. A prime number is a number that has exactly two perfect divisors. 1 is not a prime number because it has only one perfect divisor. We have seen three methods with time complexity of O(N*N), O(N*sqrt(N)) and O(N*log(log(N))). In addition, the space complexity of the first two methods is O(1), and the space complexity of the Sieve of Eratosthenes method is O(N).

The above is the detailed content of JavaScript program for counting prime numbers in a range. For more information, please follow other related articles on the PHP Chinese website!