C 언어에서 PGCD의 재귀 계산

두 정수 중 적어도 하나가 0이 아닌 경우 두 정수의 GCD(최대 공약수)는 두 숫자를 나누는 가장 큰 양의 정수 제수입니다. 예를 들어, 45와 30의 GCD는 15.

1- 모듈로를 사용하여 GCD를 찾습니다

  • a에 b의 값을 할당하고 b에 a를 나눕힌 나머지 값을 b.
  • 나머지가 0이 될 때까지 반복합니다.
pgcd 모듈로 유클리드의 확장 C++ 알고리즘

예:
PGCD 모듈로 확장 유클리드 알고리즘 예
C:

#include< stdio.h> 

int main()
{
 int a,b,r,x,y; 
 do
 scanf("%d",& a); 
 동안 (a<=0); 
 do
 scanf("%d",& b); 
 동안 (b<=0); 

 if (a> b)
 {
 x=b; 
 r=a%b; 
 }
 else
 {
 x=a; 
 r=b%a; 
 }

 while(r!=0)
 {
 y=x;
 x=r; 
 r=y%x; 
 }
 printf("%d",x); 
 0을 반환합니다. 
}

2- 재귀 뺄셈 방법으로 GCD 찾기

a와 b가 두 개의 양의 정수이면 다음과 같은 산술 속성이 있습니다.
재귀 뺄셈 PGCD< / a>< / div>
예:
재귀 빼기 PGCD 제외

재귀가 있는 PGCD 프로그램.

int PGCD(int a, int b)
{
 if(a==b)
 {
 return a; 
 } 
 else
 {
 if(a> (b)
 반환 PGCD(a-b, b); 
 else
 PGCD(a, b-a)를 반환합니다. 
 }
}
참조:
위키백과: 최대 공약수
위키백과: 유클리드의 알고리즘 확장