본문으로 이동

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

4 바이트 추가됨 ,  6년 전
잔글
편집 요약 없음
잔글
== 계산법 ==
 
두 수 a와 b의 최대공약수를 구하는 방법은 [[소인수분해소인수 분해]]를 사용하는 방법과 [[유클리드 호제법]]이 있다.
 
두 수 192와 72의 최대공약수를 소인수분해를소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수분해소인수 한다분해한다.
 
<math>192=2^6 \times 3=2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 3</math>
<math>72=2^3 \times 3^2=2 \times 2 \times 2 \times 3 \times 3</math>
 
구하고 나면, 두 소인수분해소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉 <math>2 \times 2 \times 2 \times 3=24</math> 최대공약수가 24라는 결론이 나온다.
 
 
그러나 일반적으로 소인수분해를소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.