최대공약수: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
|||
51번째 줄: | 51번째 줄: | ||
[[분류:수론]] |
[[분류:수론]] |
||
[[als:Größter gemeinsamer Teiler]] |
|||
[[ar:قاسم مشترك أكبر]] |
|||
[[az:ƏBOB]] |
|||
[[bg:Най-голям общ делител]] |
|||
[[bn:গরিষ্ঠ সাধারণ গুণনীয়ক]] |
|||
[[bs:Najveći zajednički djelilac brojeva]] |
|||
[[ca:Màxim comú divisor]] |
|||
[[cs:Největší společný dělitel]] |
|||
[[da:Største fælles divisor]] |
|||
[[de:Größter gemeinsamer Teiler]] |
|||
[[el:Μέγιστος κοινός διαιρέτης]] |
|||
[[en:Greatest common divisor]] |
|||
[[eo:Plej granda komuna divizoro]] |
|||
[[es:Máximo común divisor]] |
|||
[[et:Suurim ühistegur]] |
|||
[[eu:Zatitzaile komun handien]] |
|||
[[fa:بزرگترین مقسومعلیه مشترک]] |
|||
[[fi:Suurin yhteinen tekijä]] |
|||
[[fr:Plus grand commun diviseur]] |
|||
[[he:מחלק משותף מקסימלי]] |
|||
[[hi:महत्तम समापवर्तक]] |
|||
[[hu:Legnagyobb közös osztó]] |
|||
[[id:Faktor persekutuan terbesar]] |
|||
[[io:Maxim granda komuna divisoro]] |
|||
[[is:Stærsti samdeilir]] |
|||
[[it:Massimo comun divisore]] |
|||
[[ja:最大公約数]] |
|||
[[lt:Didžiausias bendrasis daliklis]] |
|||
[[lv:Lielākais kopīgais dalītājs]] |
|||
[[ml:ഉത്തമ സാധാരണ ഘടകം]] |
|||
[[mn:Хамгийн их ерөнхий хуваагч]] |
|||
[[ms:Faktor sepunya terbesar]] |
|||
[[nl:Grootste gemene deler]] |
|||
[[no:Største felles divisor]] |
|||
[[pl:Największy wspólny dzielnik]] |
|||
[[pms:Màssim divisor comun]] |
|||
[[pt:Máximo divisor comum]] |
|||
[[ro:Cel mai mare divizor comun]] |
|||
[[ru:Наибольший общий делитель]] |
|||
[[simple:Greatest common divisor]] |
|||
[[sk:Najväčší spoločný deliteľ]] |
|||
[[sl:Največji skupni delitelj]] |
|||
[[sq:PMP]] |
|||
[[sr:Највећи заједнички делилац]] |
|||
[[sv:Största gemensamma delare]] |
|||
[[ta:மீப்பெரு பொது வகுத்தி]] |
|||
[[te:గరిష్ఠ సామాన్య భాజకం]] |
|||
[[th:ตัวหารร่วมมาก]] |
|||
[[tr:Ortak bölen]] |
|||
[[uk:Найбільший спільний дільник]] |
|||
[[ur:عاد اعظم]] |
|||
[[vi:Ước số chung lớn nhất]] |
|||
[[yi:גרעסטער געמיינזאמער טיילער]] |
|||
[[zh:最大公因數]] |
2013년 3월 9일 (토) 02:57 판
최대공약수(最大公約數)란, 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++)
나머지를 구하는 %연산을 번갈아가며 구한다.
#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);
}