매일프로그래밍 - 최대 공약수 구하기

Q. 정수 배열이 주어지면 배열 안의 모든 정수의 최대 공약수를 구하시오.

EX.

Input : [ 3, 2, 1 ]
Output : 1

Input : [ 2, 4, 6, 8 ]
Output : 2

 

 

풀이

 

import java.util.Scanner;

 

public class javatest {

 

      public static void main(String[] args) {

 

            String[] arr = null; // 입력받은 값 구분자로 나눈 배열

            int[] arr2; // 공통 약수를 담을 배열

            String change = ""; // 교환에 사용될 변수

            int num = 0; // arr2에 사용될 인덱스

            int max = 0; // 최대 공약수

            // 정수 배열 입력받기

            System.out.println("정수 배열을 ,를 구분자로 입력해주세요.");

            Scanner scan = new Scanner(System.in);

            arr = scan.nextLine().split(","); // 입력받은 값 배열에 넣기

            arr2 = new int[Integer.parseInt(arr[0])]; // arr2 초기화

            // 첫 번째 수의 약수들 구하기

            for(int i=1; i<=Integer.parseInt(arr[0]); i++) {

                  if(Integer.parseInt(arr[0]) % i == 0) {

                        arr2[num] = i;

                        num++;

                  }

            }

            // 공약수 구하기

            for(int i=1; i<arr.length; i++) {

                  for(int j=0; j<arr2.length; j++) {

                        if(arr2[j] != 0) {

                              if(Integer.parseInt(arr[i]) % arr2[j] != 0) {

                              arr2[j] = 0;

                        }

                  }

            }

      }

      // 최대공약수 구하기

      for(int i=0; i<arr2.length; i++) {

            if(arr2[i] > max) {

                  max = arr2[i];

            }

      }

      // 출력

      System.out.println(max);

      }

}

 

 

결과