最大公約数を求めるユークリッドの互除法は、
紀元前3世紀頃にはギリシャ人のあいだに知られていた。
驚きである。
//最大公約数を求める(ユークリッドの互除法)
//再帰版
int gcd(int m, int n)
{
if (n == 0) return m;
return gcd(n, m % n);
}
//非再帰版
int gcd(int m, int n)
{
while (n > 0)
{
int r = m % n;
m = n;
n = r;
}
return m;
}
int result = gcd(954, 288); //=>18
コメント (1)
(1) X,Y in Z[Sqrt[3]];
(1 + 2*Sqrt[3])*X + (5 + 4*Sqrt[3])*Y=1
-------------------------------------------
X=____________
Y=____________
(2) x,y in Z[I] ;
(2 + 16*I)*x + (4 + 3*I)*y=1
-------------------------------------------
x=____________
y=____________
投稿者: EGCD | 2009年05月06日 10:44
日時: 2009年05月06日 10:44