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
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.
Example:
function isPrime(i) {
if (i == 2) return true;
for (let j = 2; j < Math.pow(i, 0.5) + 1; ++j) {
if (i % j === 0) return false;
}
return true;
}
function prime(n) {
let result = [];
for (let i = 2; i < Math.pow(n, 0.5); i++) {
if (n % i == 0 && isPrime(i)) result.push(i);
if (n % i == 0 && isPrime(n/i)) result.push(n/i);
}
return result.sort((a,b)=>a-b);
}
const num = 85;
console.log("Prime factors of " +
num + ": " + prime(num));
Output
Prime factors of 85: 5,17
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.
Example:
function recursivePrime(n, d) {
if (n <= 1) return [];
if (n == 2) return [2];
flag = false;
while (n % d == 0) {
n /= d;
flag = true;
}
if (flag) return [d, ...recursivePrime(n, d + 1)];
return recursivePrime(n, d + 1);
}
const num = 85;
console.log(
"Prime factors of " +
num + ": " +
recursivePrime(num, 2)
);
Output
Prime factors of 85: 5,17
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.
Example:
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