C 언어의 전전 상 제법 최대 공약수 구하 기

전전 상 제법 은 위 키 백과 에서 수학 에서 전전 상 제법, 유클리드 알고리즘 (영어: Euclidean algorithm) 이 라 고도 부 르 며 최대 공약수 를 구 하 는 알고리즘 이다.전전 상 제법 은 유클리드 의 《 기 하 본 》 (VII 권, 명제 i 와 ii) 에 처음 등장 하고 중국 에 서 는 동한 에 나타 난 《 9 장 산술 》 으로 거 슬러 올라간다.
두 정수 의 최대 공약 수 는 그것들 을 동시에 제거 할 수 있 는 가장 큰 정수 이다.전전 상 나눗셈 은 다음 과 같은 원 리 를 바탕 으로 한다. 두 정수 의 최대 공약 수 는 그 중에서 작은 수 와 두 수의 차이 의 최대 공약 수 와 같다.예 를 들 어 252 와 105 의 최대 공약수 는 21 ({\ displaystyle 252 = 21 \ \ times 12; 105 = 21 \ \ times 5} {\ displaystyle 252 = 21 \ times 12; 105 = 21 \ \ times 5}) 이다.왜냐하면× (12 − 5) = 147 이 므 로 147 과 105 의 최대 공약수 도 21 이다.이 과정 에서 비교적 큰 수가 줄 어 들 었 기 때문에 같은 계산 을 계속 하면 이 두 수 를 그 중 하나 가 0 이 될 때 까지 계속 줄 일 수 있다.이때 남 은 것 이 0 이 되 지 않 은 수 는 두 수의 최대 공약수 다.전전 상 제법 으로 도 내 놓 을 수 있 으 며, 두 수의 최대 공약수 는 두 수의 정수 배 를 더 해서 표시 할 수 있다. 예 를 들 어 21 = 5× 105 + (−2) × 252 。이 중요 한 결론 을 배 촉 의 정리 라 고 한다.현대 암호학 에 있어 서 그것 은 RSA 알고리즘 (전자상거래 에서 광범 위 하 게 사용 되 는 공개 키 암호 화 알고리즘) 의 중요 한 부분 이다.
쉽게 말 하면 전전 상 제법 의 원 리 는 다음 과 같다.

먼저 두 개의 수 를 비교 하여 첫 번 째 수 를 최대 a 로 하고 두 번 째 수 는 최소 b

이다.

최대 수% 최소 수 를 나머지 a% b = temp

후 나머지 값 을 최소 a = temp 에 부여 하고 최대 b 즉 b% a

를 제거 합 니 다.

나머지 가 0

이 되 지 않 을 때 까지 계속 왕복 했다.

#include

int main(void)
{
	int a, b, num1, num2, temp;
	
	printf("please input a number:
");
	scanf("%d%d", &num1, &num2);
	if (num1 < num2) #      
	{
		temp = num1;
		num1 = num2;
		num2 = temp;
	}
	a = num1;
	b = num2;
	while(b != 0)  #         
	{
		temp = a%b;
		a = b;
		b = temp;
	}
	printf("   ：%d
", a);
	printf("   :%d
", num1 * num2 / a);
	return 0;
 }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

데이터 구조 - C 언어 는 스 택 의 초기 화, 입, 출, 스 택 지붕 보기 등 작업 을 실현 합 니 다.

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

C 언어의 전전 상 제법 최대 공약수 구하 기

좋은 웹페이지 즐겨찾기