[js] 최대 공약수, 최소공배수 구하기 (feat. 유클리드 호제법)

공약수는 두 개 이상의 자연수의 공통된 약수이고, 공약수 중에서 가장 큰 공약수를 바로 최대공약수라 하고,

두 수의 공약수가 1밖에 없을 때 이 두 수를 서로소라고 한다.

 

12와 18의 최대공약수는?
12의 약수: 1, 2, 3, 4, 6, 12
18의 약수: 1, 2, 3, 6, 9, 18

두 수의 공약수는 1, 2, 3, 6이고 이 중 가장 큰 공약수, 최대공약수가 6

 

 

유클리드 호제법을 이용한 풀이 

- a, b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a>b)

- 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다

- 서로가 나누어지면 a%b 가 최대공약수이다. 나누어지지 않는다면 위처럼 b와 a를 b를 나눈 나머지를 다시 나눈다.

 

const solutuon = (n, m) => {
  const gcd = (a, b) => {
    if (b === 0) return a; // 나누어지면 a 리턴
    return gcd(b, a % b); // 나누어지지 않는다면 b와 a%b를 다시 나눈다
  };
  const lcm = (a, b) => (a * b) / gcd(a, b); // 두 수의 곱을 최대공약수로 나눈다.
  return console.log(
    `최대 공약수는? ${gcd(n, m)}, 최대 공배수는? ${lcm(n, m)}`
  );
};
console.log(solutuon(6, 12));

또는

let N = 24, M = 18;

function getGcd(a, b) {
  while (b !== 0) {
    n = a % b;
    a = b;
    b = n;
  }
  return a;
}

let gcd = getGcd(N, M); //최대공약수
let gcf = (N * M) / gcd; //최소공배수

 

 

 

 

유클리드 호제법(- 互除法, Euclidean Algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.

- 위키백과, 우리 모두의 백과사전.

 

 

 

약수 구하기 (배열)

function solution(num) {
	const arr = [];
    for(let i = 2; i < num; i++){
    	if(num % i === 0) {
        	arr.push(i)
        }
    }
    return arr;
}


console.log(solution(28));

 

 

 

배수 구하기 (배열)

function solution(num){
	let arr = [];
	for(let i = 0; i <= 1000; i++) {
    	if(i % num === 0 && i !== 0){
        	arr.push(i)
        }
    }
    return arr;
}

console.log(solution(50))