CODEWITHSUNDEEP
javascript
KokoBear
KokoBear

Reputation: 101

How to find the common prime factors of two numbers? javascript

I know how to find the prime factors of a number (my code is below), but I am wondering how I can find the common prime factors between two numbers? Thanks in advance!

function isPrime(number){
  if(number<= 1) return false;
  if(number===2) return true;
  else{
    for(let i=2; i<number; i++){
      if(number%i===0){
        return false;
      }
    }
    return true;
  }
}
console.log(isPrime(5)); //5

const findPrimeFactors = num => {
   const result = num % 2 === 0 ? [2] : [];
   let start = 0;
   while(start <= num){
      if(num % start === 0){
         if(isPrime(start)){
            result.push(start);
         }
      }
      start++;
   }
   return result;
}
console.log(findPrimeFactors(18)); //[2, 2, 3]
console.log(findPrimeFactors(5)); //[5]

Upvotes: 1

Views: 292

Answers (2)

vitaly-t
vitaly-t

Reputation: 25840

Efficient way of doing this, using prime-lib library:

import {primeFactors} from 'prime-lib';

const arr1 = primeFactors(6); // [2, 3]
const arr2 = primeFactors(12); // [2, 2, 3]

const commonFactors = arr1.filter(value => arr2.includes(value));

console.log(commonFactors); //=> [2, 3]

We simply find all factors for both arrays, and get values intersection.

And primeFactors in that library performs much faster than earlier implementations shown here.

Upvotes: 1

Quyết
Quyết

Reputation: 602

You can do as following:

  1. Find the greatest common divisor of 2 numbers.
  2. Factorization of the GCD is the result you want.

Note: It looks like your prime factors function is working wrong

const gcd = function(a, b) {
  if (!b) {
    return a;
  }

  return gcd(b, a % b);
}

function isPrime(number){
  if(number<= 1) return false;
  if(number===2) return true;
  else{
    for(let i=2; i<number; i++){
      if(number%i===0){
        return false;
      }
    }
    return true;
  }
}

function findPrimeFactors(n) {
  const factors = [];
  let divisor = 2;

  while (n >= 2) {
   if (n % divisor == 0) {
     factors.push(divisor);
      n = n / divisor;
   } else {
      divisor++;
   }
}
  return factors;
}

console.log(findPrimeFactors(gcd(6,12)))

Upvotes: 1

Related Questions