How to find all prime numbers less than a limit / How to create a prime number checker in javascript

On:

What is a prime number?
A prime number is a number that is completely divisible by only 1 and itself. By completely divisible means that when divided by a number, the remainder is 0.

0 is not a prime number.

In other words, a prime number is a number that has only 2 factors, 1 and the number itself. Examples of prime numbers are 2, 3, 7, 11, 13, 17, 19, 23, 29, 34 and so on.

Find all prime numbers within a limit
This post will show you how to create a javascript program that determines all the prime numbers less than a given number.
Below is a function that does this.

function getPrimeNumbers(limit) {
  // iterate from 2 till the limit
  for(let number = 2; number <= limit; number++) {
    let isPrime = true;
    // iterate from 2 till the current number to be tested
    for(let factor = 2; factor < number; factor++) {
       // check if the number has any other factor
       if(number % factor == 0) {
          isPrime = false;
          break;
       }
    }
    // print the number if it is prime
    if(isPrime) {
       console.log(number);
    }
  }
}

getPrimeNumbers(23);

Explanation
Above function contains 2 for loops with 1 nested loop. Outer for loop iterates from 2 till the number till which we need to determine prime numbers.

Inner loop is used to test whether the current number is prime or not by iterating from 2 till 1 less than the number. Thus, if the current outer loop index is 7, the inner loop will iterate from 2 to 6.
In every iteration, the number is divided by the loop variable and the remainder is checked. If the remainder is 0, means the number is completely divisible by another number other than the itself and hence it is not prime. If a number is found to be prime, there is no need to continue the loop and hence it is terminated.
Finally, if the number is prime, then it is displayed.
Output of the above program is

2
3
5
7
11
13
17
19
23

Optimization: Prime number checker
Above function contains a nested for loop which checks whether a number is prime or not. Instead of embedding it inside the outer loop, it can be pulled in another function as shown below.

function getPrimeNumbers(limit) {
  // iterate from 2 till the limit
  for(let number = 2; number <= limit; number++) {
      // print the number if it is prime
      if(isPrime(number)){
       console.log(number);
    }
  }
}

/**
* Checks for the supplied number being prime. Can be used as prime checker program
*/
function isPrime(number) {
   // iterate from 2 till the current number to be tested
   for(let factor = 2; factor < number; factor++){
       if(number % factor == 0){
          return false;
       }
   }
   // number is prime
   return true;
}

A new function isPrime is created which receives the number to be checked for prime. It iterates from 2 till 1 less than the number and checks for the number being prime as above. As soon as the number is found to be non-prime, it returns false.
This function becomes reusable and can be used to test for a prime number independently.

Leave a Reply