[Baekjoon]9417번 최대 GCD - Javascript

https://www.acmicpc.net/problem/9417

9417번: 최대 GCD

문제

정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 같다. 

출력

각 테스트 케이스마다, 입력으로 주어진 수의 모든 두 수의 쌍의 최대공약수 중 가장 큰 값을 출력한다.

예제 입력 1 복사

3
10 20 30 40
7 5 12
125 15 25

예제 출력 1 복사

20
1
25

 

문제풀이(1)

유클리드 호제법을 사용해서 각 수들의 최대공약수를 구하면되는 문제이다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());

const result = [];

const getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

for (let i = 0; i < N; i++) {
  const numbers = input[i].split(" ").map(BigInt);
  let max = 0;
  for (let j = 0; j < numbers.length; j++) {
    for (let k = j + 1; k < numbers.length; k++) {
      let gcd = getGCD(numbers[j], numbers[k]);
      if (gcd > max) max = gcd;
    }
  }
  result.push(max.toString());
}

console.log(result.join("\n"));