최대공약수: 두 판 사이의 차이

위키백과, 우리 모두의 백과사전.
내용 삭제됨 내용 추가됨
편집 요약 없음
1번째 줄: 1번째 줄:
'''최대공약수'''(最大公約數)란, [[0]]이 아닌 두 [[정수]]의 공통되는 [[약수]] 중에서 가장 큰 수를 말한다. 두 정수 ''a''와 ''b''의 최대공약수를 기호로 gcd(''a, b'')로 표기하거나, 더 간단히 (''a, b'')로도 표기한다.
'''최대공약수'''(最大公約數)란, [[0]]이 아닌 두 [[정수]]의 공통되는 [[약수]] 중에서 가장 큰 수를 말한다. 두 정수 ''a''와 ''b''의 최대공약수를 기호로 gcd(''a, b'')로 표기하거나, 더 간단히 (''a, b'')로도 표기한다.


만약 두 정수의 최대공약수가 1과 -1밖에 없는 경우, 이 두 수는 [[서로소 (수론)|서로소]]라고 부른다.
만약 두 정수의 최대공약수가 1인 경우, 이 두 수는 [[서로소 (수론)|서로소]]라고 부른다.


== 성질 ==
== 성질 ==

2012년 2월 6일 (월) 22:15 판

최대공약수(最大公約數)란, 0이 아닌 두 정수의 공통되는 약수 중에서 가장 큰 수를 말한다. 두 정수 ab의 최대공약수를 기호로 gcd(a, b)로 표기하거나, 더 간단히 (a, b)로도 표기한다.

만약 두 정수의 최대공약수가 1인 경우, 이 두 수는 서로소라고 부른다.

성질

  • gcd(a, b)는 ab의 약수이다.
  • 두 수의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다.
    gcd(a, b)·lcm(a, b) = a·b
  • a와 b의 최대공약수 gcd(a, b)의 값은 ax + by 꼴의 수(x, y는 정수) 중 가장 작은 양수의 값과 같다.


컴퓨터 프로그래밍(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;
}

컴퓨터 프로그래밍(Java)

public static int gcd(int p, int q)
{
    if (q == 0) return p;
    int r = p % q;
    return gcd(q, r);
}

같이 읽기