C言語におけるPGCDの再帰的計算

1- Modulo

• a に b の値を代入し、b に b に対する a の除算の剰余の値を代入します。
• 余りがゼロになるまで繰り返します<。>

例:

#include

int main()
{
 int a,b,r,x,y;
 do
 scanf("%d",&a);
 while (a<=0);
 do
 scanf("%d",&b);
 while (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を見つけます

int PGCD(int a, int b)
{
 if(a==b)
 {
 return a; 
 } 
 else
 {
 if(a>(b)
 return PGCD(a-b, b);
 else
 return PGCD(a, b-a);
 }
}