최대공약수 최소공배수 구하기
작성자 : 김영철
등록날짜 : 2009.01.15 13:07
[개론]
유클리드호제법을 이용한 최대공약수와 최소공배수를 구하는 문제입니다.
[증명]
두 자연수 A, B
두 자연수의 최대공약수 G, 최소공배수 L
A = aG, B = bG(a, b는 서로소) 로 표현이 가능하다.
A = BQ+R(Q는 몫 R나머지)일때,
aG = bGQ+R
R = (a-bQ)G로 표현이 가능하다.
※ A, B의 최대공약수 'G' 는 B, R의 최대공약수'G'이다.
[C언어 알고리즘]
#include<stdio.h>
void main(void)
{
int num1, num2, remainder, num1num2;
printf("두 정수를 입력해 주세요...\n"); scanf("%d%d", &num1, &num2);
num1num2 = num1*num2;
while(num2){
remainder = num1%num2;
num1 = num2;
num2 = remainder;
}
printf("최대공약수는 %d\n", num1);
printf("최소공배수는 %d\n", num1num2/num1);
}
"쇼핑몰·홈페이지·오픈마켓
블로그·페이스북·이메일 등의 각종 마케팅 글쓰기, 각종 광고, 영업, 판매, 제안서, 전단지 반응율 3배×10배 이상 높이는 마법의 8단계 공식" |
☞자세히보기 |
|
|