JavaScript Program to Print All Prime Numbers in an Interval - Coding

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); 
}

Output

Time Complexity: O(N²), 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); 
    } 
}

Output

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);

Output

Prime numbers between 10 and 20 (Sieve of Eratosthenes - Optimized):
11
13
17
19

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
JavaScript Program to Generate a Range of Numbers and Characters
How to Get Last Week's Date using JavaScript ?
Matrix Chain Multiplication by using JavaScript
How to Calculate the Cumulative Sum of Elements in an Array using JavaScript?
What is Bitmasking in JavaScript?

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	9