The greatest common divisor (GCD) of two or more integers, which are not all
zero,is the largest positive integer that divides each of the integers.For two
integers
x, y, the greatest common divisor of x and y is denoted gcd(x,y).
e.g. The GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4.
How to find gcd o two integer in javascript:
Solution 1:
Code:
let gcd = function (a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
};
let gcdVal = gcd(180,90)
console.log(gcdVal)
Output:
90
Solution 2:
let numbers = [90, 180];
//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 = [];
for (let i = 0; i < numbers.length; i++) {
primeDivisors.push(getPrimeDivisors(numbers[i]));
}
console.log("Prime Divisors",primeDivisors)
let primeDivisorOfFirst = Object.keys(primeDivisors[0]);
let primeDivisorOfSecond = Object.keys(primeDivisors[1]);
var common = [];
for (let i = 0; i < primeDivisorOfFirst[i]; i++) {
let key = primeDivisorOfFirst[i];
let max = 1;
if (primeDivisorOfSecond.includes(key)) {
max = Math.min(
primeDivisors[0][key]["power"],
primeDivisors[1][key]["power"]
);
let item = {};
item[key] = { power: max };
common.push(item);
}
}
console.log("Common Divisor",common)
let gcd = common.reduce((acc, m) => {
let key = Object.keys(m)[0];
acc = acc * key ** m[key]["power"];
return acc
}, 1);
console.log(gcd);
Output:
90
LCM : The least common multiple of two integers a and b,usually denoted by
lcm(a, b), is the smallest positive integer that is divisible by both a
and b.
Formula : a * b = gcd(a,b) * lcm(a,b)
Here a & b are positive integers.
How to find LCM of two numbers ?
Solution:
let gcd = function (a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
};
let lcm = function(a,b){
return (a*b)/gcd(a,b)
}
console.log("Numbers:180,90")
let lcmVal = lcm(180,90)
console.log("LCM=",lcmVal)
Output:
Numbers:180,90
LCM= 180
How to find gcd of array of elements in javascript?
Solution:
let nums = [2, 4, 6, 8];
let gcd = function (a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
};
let findGCD = function (nums) {
let first = nums[0];
let gcdOfArray = nums.reduce((acc, elem) => {
acc = gcd(acc, elem);
return acc;
}, first);
return gcdOfArray;
};
var myGCD = findGCD(nums);
console.log(myGCD);
Output:
2
Can we write code in javascript to get GCD of two numbers without using
recursion?
Solution:
let gcdWithoutRecursion = function (a, b) {
console.time();
let min = Math.min(a, b);
let max = Math.max(a, b);
let result = 1;
if (a % b == 0 || b % a == 0) {
return min;
} else {
for (let i = min; i >= 1; i--) {
if (max % i == 0 && min % i == 0) {
result = i;
break;
}
}
console.timeEnd();
return result;
}
};
let gcdValWithoutRecursion = gcdWithoutRecursion(6800, 2100);
console.log("Result:", gcdValWithoutRecursion);
Output:
default: 0.071ms
Result: 100
Note:
Two integers a and b are coprime, relatively prime or mutually prime if
the only positive integer that is a divisor of both of them is 1.Consequently,
any prime number that divides a does not divide b, and vice versa. This is
equivalent to their greatest common divisor (GCD) being 1.One says also a
is prime to b or a is coprime with b.
No comments:
Post a Comment