In this article, we will explore a JavaScript program to find and print all prime numbers within a given range. A prime number is a natural number greater than 1, which is only divisible by 1 and itself. The first few prime numbers are 2 3 5 7 11 13 17 19 23…, The program efficiently identifies and displays prime numbers within the specified range.
prime numbers
There are several methods that can be used to Print All Prime Numbers in an Interval.
- Using Trial Division Method
- Optimized Solution
- Using the Sieve of Eratosthenes” algorithm
We will explore all the above methods along with their basic implementation with the help of examples.
Approach 1: Using the Trial Division Method in JavaScript
In this approach, we will check divisibility for each number in the interval. In the below program, the range of numbers is taken as input and stored in the variables ‘a’ and ‘b’. Then using a for-loop, the numbers between the interval of a and b are traversed.
Example:
Javascript
let a, b, i, j, flag; a = 2 b = 11 for (i = a; i <= b; i++) { if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; for (j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) console.log(i); } |
2 3 5 7 11
Time Complexity: O(N2), Where N is the difference between the range
Auxiliary Space: O(1)
Approach 3: Using Optimised Solution
In this approach, we will use the fact that even numbers (except 2) cannot be prime can significantly optimize the process of finding prime numbers within a specified interval.
Example:
Javascript
let a, b, i, j; a = 5; b = 27; if (a <= 2) { a = 2; if (b >= 2) { console.log(a); a++; } } // Make sure that a is odd before // we begin the loop if (a % 2 == 0) a++; // Note: We traverse through odd numbers only for (i = a; i <= b; i = i + 2) { // flag variable to tell // if i is prime or not let flag = 1; // Traverse till square root of j // (Largest possible value of a prime factor) for (j = 2; j * j <= i; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) { if (i == 1) continue; else console.log(i); } } |
5 7 11 13 17 19 23
Time Complexity: O(N*sqrt(N)), Where N is the difference between the range
Auxiliary Space: O(1)
Approach 2: Using the Optimized Sieve of Eratosthenes Algorithm
The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given number by eliminating multiples of each prime iteratively.
Example: In this example we are using the optimized Sieve of Eratosthenes algorithm to find and print prime numbers within the user-provided interval, efficiently identifying primes and displaying them.
Javascript
function sieveOfEratosthenesOptimized(start, end) { const primes = new Array(end + 1).fill(true); primes[0] = primes[1] = false; for (let i = 2; i * i <= end; i++) { if (primes[i]) { for (let j = i * i; j <= end; j += i) { primes[j] = false; } } } for (let i = Math.max(2, start); i <= end; i++) { if (primes[i]) console.log(i); } } // Take input from the user using prompt const startInterval = 10; const endInterval = 20; // Execute the function with user-provided interval console.log("Prime numbers between", startInterval, "and", endInterval, "(Sieve of Eratosthenes - Optimized):"); sieveOfEratosthenesOptimized(startInterval, endInterval); |
Prime numbers between 10 and 20 (Sieve of Eratosthenes - Optimized): 11 13 17 19