Categories
28°C, New York
Home Javascript Sieve of Eratosthenes Algorithm

Sieve of Eratosthenes Algorithm

Method 2: Recursive Approach with Spread Operator

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer. We can modify this algorithm slightly to find the prime factors of a given number.

Example:

JavaScript 
function primeFactorsSieve(n) {
    const primes = [];
    const smallestPrimeFactor = new Array(n + 1).fill(0);
    
    for (let i = 2; i <= n; ++i) {
        if (smallestPrimeFactor[i] === 0) {
            smallestPrimeFactor[i] = i;
            primes.push(i);
        }
        
        for (let j = 0; j < primes.length && primes[j] <= smallestPrimeFactor[i] && i * primes[j] <= n; ++j) {
            smallestPrimeFactor[i * primes[j]] = primes[j];
        }
    }
    
    const factors = [];
    while (n > 1) {
        factors.push(smallestPrimeFactor[n]);
        n /= smallestPrimeFactor[n];
    }
    
    return factors;
}

const num = 85;
console.log("Prime factors of " + num + ": " + primeFactorsSieve(num));

Output
Prime factors of 85: 5,17


JavaScript Program to Find Prime Factors

In this article, we will see all the methods to find the prime factors of a number using JavaScript.

Methods to Find Prime Factors:

Table of Content

  • Using loops and Math.pow() Method
  • Recursive Approach with Spread Operator
  • Sieve of Eratosthenes Algorithm

Similar Reads

Method 1: Using loops and Math.pow() Method

In this method, we will use a JavaScript loop to iterate the possible factors and Math.pow() method to get the square root of the number. Instead of Math.pow() method, we can also use Math.sqrt() or i*i < n condition....

Method 2: Recursive Approach with Spread Operator

In this method, we will call the function recursively and return the output with the spread operator to get the array output....

Method 3: Sieve of Eratosthenes Algorithm

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a specified integer. We can modify this algorithm slightly to find the prime factors of a given number....

Tags:
#JavaScript-DSA #JavaScript-Program #JavaScript #Web Technologies

Method 2: Recursive Approach with Spread Operator