|
程そ计
ㄢ俱计 A 籔 B ぇ程そ计计厩﹚竡
| 璝Τ计 p 俱埃 A 籔 B玥 p 嘿 A 籔 B そ计 |
| 礛τ渤そ计い程嘿 A B ㄢ计程そ计 |
劣锣埃猭(稼碭ń眔衡玥Euclidean algorithm)璶瞶阶
璝 r A 埃 B 緇计玥 A 籔 B そ计ゲ籔 B 籔 r そ计
ㄒ
A=60B=36
玥 r = 24
A 籔 B そ计 2, 3, 4, 6, 12
B 籔 r そ计 2, 3, 4, 6, 12
ㄢЧ (ǎ劣锣埃猭闽靡)
琂礛 A 籔 B そ计穦籔 B 籔 緇计 r そ计玥ノ瞶盢 B 籔 r 蠢传Θ穝 A 籔 B玻ネ穝 rㄌ摸崩 r 箂琌碞琌程そ计?
ㄒ簍絤
A=60B=36 眔 r = 24
A=36B=24 眔 r = 12
A=24B=12 眔 r = 0
眔程そ计 12
A 璝 B 猭ョ
A=36B=60 眔 r=36
A=60B=36 眔 r=24 ()
パ璝ㄧ计 gcd(a,b) 琌― a 籔 b 程そ计玥 gcd(a,b) = gcd(b,r)讽 r = 0 b A 籔 B 程そ计
|
患癹ㄢ璶
A.gcd (a , b) 籔 gcd(b , r) 闽玒 gcd(a , b) = gcd(b,a%b)
B.sum(b , 0) = b
癹伴 |
|
患癹 |
#include <stdio.h>
#include <stdlib.h>
int main(){
int i, a, b, r;
scanf("%d %d",&a,&b);
printf("gcd(%d,%d) =",a,b);
r=a%b;
while(r!=0){
a=b;
b=r;
r=a%b;
}
printf("%d\n",b);
return(0);
} |
|
#include <stdio.h>
#include <stdlib.h>
int gcd(int a , int b){
if(b==0)
return(a);
else
return(gcd(b , a%b));
}
int main(){
int a, b, k;
scanf("%d %d",&a, &b);
k=gcd(a, b);
printf("gcd(%d,%d) = %d\n",a,b,k);
return(0);
} |
|