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
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
Contact Us