c언어 최대공약수 c언어 최소공배수 / c언어 최소공배수 최대공약수 / c언어 최대공약수 소스 / c언어 최소공배수 소스

c언어로 최대공약수 최소공배수를 구하겠습니다.

c언어 최대 공약수 / 최소 공배수 알고리즘 개념

우선 c언어로 최대공약수, 최소공배수를 구하기 전에 개념을 알아야 겠죠(아시는 분은 스킵하셔도 됩니다)

최대공약수란 입력받은 숫자를 나눌 수 있는 수중 가장 큰 수

최소공배수란 입력받은 두 수의 배수 중 공통되는 가장 작은수를 의미합니다.

손으로 풀면 주로 저런방법으로 풀죠 ?(다들 저렇게 배우셨죠?)

공통으로 나누어지는 수로 값을 나누고 그 몫을 아래에 적으면서, 공통으로 나눠지는 수가 1밖에 없을때까지 계속 반복합니다.

그리고 나오게 되는 수에서 왼쪽에 있는 수들을 곱하게 되면 최대공약수

최대공약수와에 나눠지지 않는 최종값들(아래쪽의 수)까지 곱하면 그 값이 최소공배수가 됩니다.

c언어로 만든 최대공약수 / 최소공배수도 이 방법을 사용하였습니다.

C언어 최대공약수 / 최소공배수 소스

#include <stdio.h>

 

/*

        최대공약수 , 최소공배수 구하는 프로그램

*/

main()

{

        int num_1, num_2;

        int max=1, min=1;

        int count;

        int flag = 1;          //while문을 빠져나오기 위한 flag

        printf("숫자를 두개 입력하세요 : ");

        scanf_s("%d %d", &num_1, &num_2);     //두 수를 입력 받는다.

 

        /*

        두 수 중 작은수를 count로 한다.

        */

        if (num_1 > num_2) {

               count = num_2;

        }

        else{

               count = num_1;

        }

 

        while (flag == 1){

               for (int i = count; i >= 1; i--) {          

                       if (i == 1){                  //i가 1까지 도달했다는 것은 1말고 공통으로 두 수를 나눌 수 있는 수가 없다는 것이다.

                              flag = 0;                     //flag값 변경 -> while문 빠져나온다

                              min = max * num_1 * num_2;

                              break;

                       }

                       if (num_1 % i == 0) {

                              if (num_2 % i == 0) {

                                      max = max * i;        

                                      num_1 = num_1 / i;     //num_1 값을 변경

                                      num_2 = num_2 / i;     //num_2 값을 변경

 

                                      if (num_1 > num_2) {

                                             count = num_2;

                                      }

                                      else{

                                             count = num_1;

                                      }

 

                                      continue;              //continue문을 사용하여 다시 처음부터 for문을 돌린다

                              }

                       }

               }

        }

       

       

        printf("최대공약수 : %d\n", max);

        printf("최소공배수 : %d\n", min);

 

}

C언어 최대공약수 / 최소공배수 소스 출력 결과

C언어 최대공약수 / 최소공배수 소스 설명

두 수를 입력받고, 작은 수를 count로 정합니다. 만약 100과 50을 입력받았다고 하면 51은 두 수를 공통으로 나눌수 없기 때문에, 50까지만 하면 되죠? 

그렇기 때문에 작은수부터(100과 50이라면 50)시작하여 1까지만 하면 됩니다.

작은수보다 큰 수로 그 값을 나눌수 없기 때문이죠 ~

if문을 사용하여 두 수중 하나의 수를 mod연산해봅니다. mod연산의 값이 0 이라면(나눠진다면) 이제 그 값으로 남은 하나의 값을 mod해봅니다.

공통으로 두 수를 나눌수 있다는 것은, 두 수중 하나의 수라도 나누지 못한다면 충족하지 못하기때문에, 두개의 if문을 모두 통과한 수에 한해서만, 다음 연산을 수행합니다.

이 두개의 if문을 통과한 i는 위 알고리즘 설명하면서 첨부했던 그림의 왼쪽에 해당하는 숫자들 입니다.

2, 2 / 2, 2

입력받은 숫자 혹은 몫으로 나온 숫자를 공통으로 나눌 수 있는 수에 해당하죠

이 값들을 모두 곱한것이 max, 최대공약수가 됩니다.

그리고 num_1, num_2, 즉 입력받은 수를 i로 나눠준 값을 다시 num_1, num_2로 설정합니다.

위의 그림을 예로 든다면 6, 8 / 3, 4 이런애들이죠

ex)12 16을 입력받았다면

1. count값은 12로 설정 (12 < 16이니까, 즉 12가 16보다 작으니까)

2. i는 12부터 1까지 하나씩 줄여가며 num_1(12), num_2(16)를 공통으로 나눌 수 있는 수를 구한다

3. i는 4일때, 공통으로 나누어진다. 그렇게 되면 max = 1(초기max값) * i(4)가 되어 max는 4가 된다.

num_1 = num_1/i로 3, num_2 = num_2/i로 4가 된다.

4. 다시 두 수를 비교 count값은 3이 된다.

5. i는 3부터 하여 2번항목부터 반복

6. i의 값이 1이 된다면 -> 이말은 즉, 두수를 공통으로 나누는 수가 1밖에 없다는 것 = 공통으로 나눌 수 있는 수가 없다 라고 할 수 있다.

7. 그렇게 되면 flag값을 0으로 변경해준다(무한 반복되는 while문을 빠져나오기 위해)

8. 최소공배수 = max * num_1 * num_2이다.(알고리즘 설명 그림에서 빨간색 펜 부분)

9. break문을 통해 for문을 빠져나오고, flag값이 0이기때문에 while문을 빠져나온다.

10. 결과 출력

이상으로 c언어 최대공약수 / 최소공배수 를 구하는 포스팅을 마치겠습니다.

궁금하시거나 오류가 있으면 댓글 달아주세요 ~

감사합니당.