문제 6 - 최대공약수

문제 : 두 수의 최대 공약수를 구하세요.

 

Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();

		List<Integer> list = new ArrayList<Integer>();
		for(int i=2; i<=n1; i++) {
			
			if(n1 % i == 0) {
				list.add(i);
			}
		}
		
		List<Integer> list2 = new ArrayList<Integer>();
		for(Integer i : list) {
			if(i<=n2 && (n2 % i == 0)) {
				list2.add(i);
			}
		}

		int maxValue = 0;
		for(Integer i : list2) {
			maxValue = Math.max(maxValue, i);
		}
		if(maxValue != 0) {
			System.out.println("최대 공약수 : " + maxValue);
		}else {
			System.out.println("없음");
		}
		
		// 강의 정답
		/*
		 * 최대 공약수를 알려면, 두 수중 큰 수를 알아야함.
		 * 큰 수와, 작은수가 해당 값(최대 공약수)으로 나누어 지는지 확인
		 */
		
		int small;
		int big;
		if(n1 > n2) {
			small = n2;
			big = n1;
		}else {
			small = n1;
			big = n2;
		}
		
		int gcd = 1; // 최대공약수
		for(int i=1; i<=small; i++) {
			if(big % i == 0 && small %i == 0) {
				gcd = i;
			}
		}
		System.out.println(gcd);

 

강의 정답이 훨씬 깔끔하네. 두 수중 큰 수를 알면 더 쉽게 문제를 해결 할 수 있다.

 

출처 : https://www.youtube.com/watch?v=jdnGckTvZ64&list=PLVoihNyHW4xkm_KJ8_N8X7F6EQP4uSRyR&index=7