Check a number is Prime or not using JavaScript
We are given a positive integer N and the task is to find out whether the given number is prime or not. A prime number is a number that is divisible by 1 and itself only.
Examples:
Input: N = 4 Output: Not Prime Explanation: The given number 4 is also dividble by 2 other than 1 and itself. Input: 5 Output: Prime Explanation: 5 can only be divisible by 1 and itself.
These are the following ways to solve this problem:
Table of Content
- Checking prime number using Flag variable
- Using the root value of given number
- Using recursive approach
- By reducing iterations in the loop
- Using Regular Expression
Checking prime number using Flag variable
In this approach, we create a function and use for loop with a flag varibale which will be set to false if the number is not prime and show the result on the user screen based on the value of flag variable.
Example: This example shows the implementation of the above-explained approach.
// Function to check prime number
function checkPrime(num) {
let i, flag = true;
for (i = 2; i <= num - 1; i++) {
if (num % i == 0) {
flag = false;
break;
}
}
if (flag == true)
console.log(num + " is prime");
else
console.log(num + " is not prime");
}
checkPrime(4);
checkPrime(5);
Output
4 is not prime 5 is prime
Time Complexity: O(n)
Auxiliary Space: O(1)
Using the root value of given number
We can use square root value of the given number to check if it is prime. Because, if we represent a number as product of two numbers as n=a*b, then any one of a and b will be smaller than square root of n. If the number is divisible by any one of them, then it will be a prime number.
Example: This example shows the implementation of the above-explained appraoch.
function checkPrime(num){
let res = true;
if(num<=1){
res = false;
}
for(let i=2; i*i<=num; i++){
if(num%i===0){
res = false;
break;
}
}
if(res){
console.log(num, " is a prime number.");
}
else{
console.log(num, " is not a prime number.");
}
}
checkPrime(4);
checkPrime(5);
Output
4 is not a prime number. 5 is a prime number.
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Using recursive approach
We will create a method which will call itself again and again to check whether the passed number is prime or not.
Example: The below code implements the recursive method to check if the number is prime or not.
function checkPrime(num, div = 2) {
if (num <= 1) {
return false;
}
if (div > Math.sqrt(num)) {
return true;
}
if (num % div === 0) {
return false;
}
else {
return checkPrime(num, div + 1);
}
}
console.log(checkPrime(5) ? "Passed number is Prime" :
"Passed number is not Prime");
console.log(checkPrime(4) ? "Passed number is Prime" :
"Passed number is not Prime");
Output
Passed number is Prime Passed number is not Prime
By reducing iterations in the loop
We can optimize our code by directly terminating iterations for some numbers like 1, 2, and 3. By doing this, we can start iteration from 5 and go till sqrt(num). We will increment the iterator value with 6 everytime, because the prime numbers can be expressed as 6n+1 or 6n-1.
Example: The below code will explain the above approach with its practical implementation.
function checkPrime(num) {
// Conditions to reduce iterations
if (num <= 1)
return false;
if (num == 2 || num == 3)
return true;
if (num % 2 == 0 || num % 3 == 0)
return false;
// Incrementing iterator with 6 to reduce iterations
for (let i = 5; i * i <= num; i = i + 6)
if (num % i == 0 || num % (i + 2) == 0)
return false;
return true;
}
checkPrime(4) ? console.log("Passed number is prime") :
console.log("Passed number is not prime");
checkPrime(5) ? console.log("Passed number is prime") :
console.log("Passed number is not prime");
Output
Passed number is not prime Passed number is prime
Using Regular Expression
The Regular Expression approach for checking prime numbers in JavaScript involves testing if the number is a prime using a regular expression pattern. The pattern `/^1?$|^(11+?)\1+$/` evaluates true if the number is prime and false otherwise.
Example: In this example we are following above explained apporach.
function isPrimeRegExp(num) {
return !/^1?$|^(11+?)\1+$/.test('1'.repeat(num));
}
console.log(isPrimeRegExp(17)); // Output: true
console.log(isPrimeRegExp(3)); // Output: true
console.log(isPrimeRegExp(8)); // Output: false
console.log(isPrimeRegExp(15)); // Output: false
Output
true true false false
Sieve of Eratosthenes Algorithm
The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer. It works by iteratively marking the multiples of each prime number starting from 2 as composite (not prime). After processing all numbers up to the square root of the given number, the remaining unmarked numbers are primes.
Example: The provided code defines sieveOfEratosthenes(n) to generate an array marking primes up to `n`, and isPrime(n) to check if `n` is prime using the Sieve of Eratosthenes algorithm.
function sieveOfEratosthenes(n) {
let prime = new Array(n + 1).fill(true);
prime[0] = prime[1] = false;
for (let p = 2; p * p <= n; p++) {
if (prime[p]) {
for (let i = p * p; i <= n; i += p) {
prime[i] = false;
}
}
}
return prime;
}
function isPrime(n) {
if (n <= 1) return false;
let primes = sieveOfEratosthenes(n);
return primes[n];
}
console.log(isPrime(7));
console.log(isPrime(12));
Output
true false
Contact Us