문제
정수 A와 B의 최대 공약수를 구하는 코드를 작성하세요.
위 문제를 해결하기 위해 우선 최대 공약수 정의에 대해 살펴보겠습니다.
- 두 정수 A,B의 공약수 중 가장 큰 수
공약수란?
- 두 정수 A와 B가 공통으로 가지고 있는 약수
약수란?
- 두 정수 , 에 대하여 를 만족하는 정수 가 존재한다면, 를 의 약수라고 한다.
- 즉, 를 로 나누었을 때 나머지가 0이면, 를 의 약수라고 한다.
최대 공약수 예제를 반복문으로 해결하기 위해 다음 3가지를 정리해야 합니다.
1. 반복횟수 : 초기화, 조건식, 증감연산식을 결정
2. 규칙성 : 실행문을 결정
3. 반복문 종료 후 작업
1. 반복횟수
- 두 정수의 최대 공약수를 찾기 위해서, 두 정수의 공약수를 찾아야 합니다.
- 아래 내용을 보면 8과 12의 공약수를 구하는 과정이 나와 있습니다.
- 아래와 같이 8보다 큰 9부터는 비교할 필요가 없습니다. 왜냐하면 9부터는 8을 나누었을 때 나머지가 8로 고정이기 때문입니다.
- 따라서 반복횟수는 1부터 작은수까지 1씩 증가하면 됩니다.
- 초기화 : i = 1
- 조건식 : i <= 작은수
- 증감연산식 : i++ 또는 ++i 또는 i+=1
8의 약수 : 1, 2, 4, 8
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
나머지 |
0 |
0 |
2 |
0 |
3 |
2 |
1 |
0 |
8 |
8 |
8 |
8 |
- 나머지 : 8를 i로 나누었을 때 나머지
12의 약수 : 1, 2, 3, 4, 6, 12
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
나머지 | 0 | 0 | 0 | 0 | 2 | 0 | 5 | 4 | 3 | 2 | 1 | 0 |
- 나머지 : 12를 i로 나누었을 때 나머지
8과 12의 공약수 : 1, 2, 4
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
mod A |
0 |
0 |
2 |
0 |
3 |
2 |
1 |
0 |
8 |
8 |
8 |
8 |
mod B |
0 |
0 |
0 |
0 |
2 |
0 |
5 |
4 |
3 |
2 |
1 |
0 |
- mod A : 8를 i로 나누었을 때 나머지
- mod B : 12를 i로 나누었을 때 나머지
2. 규칙성
- i가 A와 B의 공약수이면 최대 공약수를 저장하는 변수에 i를 저장합니다.
- 공약수를 작은 수부터 구하기 때문에 공약수들을 변수에 덮어쓰기를 하면 마지막에 남은 공약수는 가장 큰 공약수가 됩니다.
- 조건식 : A를 i로 나누었을 때 나머지가 0과 같고(i가 A의 약수이다) B를 i로 나누었을 때 나머지가 0과 같다(i가 B의 약수이다)
=> A % i == 0 && B % i == 0
- 조건식 실행문 : 최대 공약수 변수에 i를 저장 => gcd = i
3. 반복문 종료 후 작업
- 최대 공약수 gcd를 출력
정리한 내용을 바탕으로 소수 판별 예제 코드는 아래와 같습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <stdio.h> int main() { int A = 8, B = 12; //A와 B중 작은 수를 num에 저장 int num = A>B?B:A; //최대 공약수 int gcd = 1; //반복문에서 사용할 변수 int i; for (i = 1; i <= num; i++) { if (A % i == 0 && B % i == 0) { gcd = i; } } printf("%d와 %d의 최대 공약수 : %d\n", A, B, gcd); return 0; } |
질문은 댓글로 남겨세요. 도움이 되셨다면 광고 클릭!