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.
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.
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.