최대공약수: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 문서 정리 |
잔글 →컴퓨터 프로그래밍 |
||
12번째 줄: | 12번째 줄: | ||
나머지를 구하는 %연산을 번갈아가며 구한다. |
나머지를 구하는 %연산을 번갈아가며 구한다. |
||
다음은 재귀 호출을 사용한 간단한 구현이다(C/C++/C#/Java |
다음은 재귀 호출을 사용한 간단한 구현이다(C/C++/C#/Java). |
||
<source lang=" |
<source lang="c"> |
||
int gcd(int p, int q) |
int gcd(int p, int q) |
||
{ |
{ |
||
38번째 줄: | 38번째 줄: | ||
return a; |
return a; |
||
} |
} |
||
int main() { |
int main() { |
||
std::cout << "gcd(2,4) = " << gcd(2,4) << std::endl; |
std::cout << "gcd(2,4) = " << gcd(2,4) << std::endl; |
2013년 8월 27일 (화) 18:40 판
최대공약수(最大公約數)란, 0이 아닌 두 정수나 다항식의 공통되는 약수 중에서 가장 큰 수를 말한다. 두 정수 a와 b의 최대공약수를 기호로 gcd(a, b)로 표기하거나, 더 간단히 (a, b)로도 표기한다.
특징
- gcd(a, b)는 a와 b의 약수이다.
- 두 수 또는 다항식의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다.
- gcd(a, b)·lcm(a, b) = a·b
- a와 b의 최대공약수 gcd(a, b)의 값은 ax + by 꼴의 수(x, y는 정수) 중 가장 작은 양수의 값과 같다.
- 만약 두 정수의 최대공약수가 1과 -1밖에 없는 경우, 이 두 수는 서로소라고 부른다.
- 만약 두 다항식의 상수 이외의 최대공약수가 없을 경우, 이 두 다항식은 서로소라고 부른다.
컴퓨터 프로그래밍
나머지를 구하는 %연산을 번갈아가며 구한다.
다음은 재귀 호출을 사용한 간단한 구현이다(C/C++/C#/Java).
int gcd(int p, int q)
{
if (q == 0) return p;
int r = p % q;
return gcd(q, r);
}
다음은 재귀 호출 대신 while 루프로 대체하고 제네릭 프로그래밍을 적용한 C++ 구현이다.
#include <utility>
#include <iostream>
template <class _Ty>
_Ty gcd(_Ty a, _Ty b) {
if ( a < b ) std::swap(a,b);
while ( b > 0 ) {
_Ty c = b;
b = a % b;
a = c;
}
return a;
}
int main() {
std::cout << "gcd(2,4) = " << gcd(2,4) << std::endl;
return 0;
}