Problem Statement:
For fiven number n find all its prime divisors with their corresponding power.
e.g.
Example 1:
input =45
output = (3**2) * (5**1)
Example 2:
input =100
output = (2**2) * (5**2)
Solution:
let num = 90;
//1 is not prime
function isPrime(num) {
if (num == 1) {
return false;
} else {
let max = Math.sqrt(num);
for (let i = 2; i <= max; i++) {
if (num % i === 0) return false;
}
return num > 1;
}
}
function getPrimeDivisors(num) {
let result = [];
if (num == 1) {
return [1];
} else {
let max = Math.sqrt(num);
let isOdd = num % 2; //for odd number reminder 1
let i = 1;
while (i <= max) {
if (num % i == 0 && isPrime(i)) {
result.push(i);
}
if (isOdd == 1) {
i += 2;
} else {
i++;
}
}
return result;
}
}
function getMultiplicationFactorsWithPower(num, primeDivisors) {
let factorWithPower = [];
for (let i = 0; i < primeDivisors.length; i++) {
let primeDivisor = primeDivisors[i];
let j = 2;
let maxPower = 1;
while (j < Math.sqrt(num)) {
let powerOfDivisor = Math.pow(primeDivisor, j);
if (num % powerOfDivisor == 0) {
maxPower = j;
} else {
break;
}
/*
suppose input number is 100
its prime factors are [2,5]
for prime factor 2 we need to find highest power of 2 that can divide 100
*/
j++;
}
factorWithPower.push([primeDivisors[i], maxPower]);
}
return factorWithPower;
}
let primeDivisors = getPrimeDivisors(num);
console.log("PrimeFactors:", primeDivisors);
let factorWithPower = getMultiplicationFactorsWithPower(num, primeDivisors);
var result = factorWithPower.reduce((acc, m) => {
if (acc == "") {
acc = acc + "(" + m[0].toString() + "**" + m[1].toString() + ")";
} else {
acc = acc + "*" + "(" + m[0].toString() + "**" + m[1].toString() + ")";
}
return acc;
}, "");
console.log("FactorWithPower:", factorWithPower);
console.log(`${num} = ${result}`);
Output:
PrimeFactors: [ 2, 3, 5 ]
FactorWithPower: [ [ 2, 1 ], [ 3, 2 ], [ 5, 1 ] ]
90 = (2**1)*(3**2)*(5**1)
Solution 2:
let num = 90;
//1 is not prime
function isPrime(num) {
if (num == 1) {
return false;
} else {
let max = Math.sqrt(num);
for (let i = 2; i <= max; i++) {
if (num % i === 0) return false;
}
return num > 1;
}
}
//num is 1 then it will not have any prime divisor
function getPrimeDivisors(num) {
let result = {};
let max = Math.sqrt(num);
let isOdd = num % 2; //for odd number reminder 1
let i = 1;
while (i <= max) {
if (num % i == 0 && isPrime(i)) {
/*find all powers of this prime*/
let j = 2;
let maxPower = 1;
while (j < Math.sqrt(num)) {
let powerOfDivisor = Math.pow(i, j);
if (num % powerOfDivisor == 0) {
maxPower = j;
} else {
break;
}
j++;
}
let item ={ power: maxPower } ;
result[i] = item
}
if (isOdd == 1) {
i += 2;
} else {
i++;
}
}
return result;
}
let primeDivisors = getPrimeDivisors(num);
console.log("PrimeFactors:", primeDivisors);
Output:
PrimeFactors: { '2': { power: 1 }, '3': { power: 2 }, '5': { power: 1 } }
No comments:
Post a Comment