歐幾里得算法

鎖定

歐幾里得算法

a = bh0 + r0，其中 r0 ＜ b.

歐幾里得算法(2張)

因此若令 m = - h1 且 n = 1 + h0h1，則 d = r1 = ma + nb. 依照此法，當 r0,r1 和 r2 皆不為 0 時，由於 d = gcd(a,b) = rn - 1 故由 rn - 3 = rn - 2hn - 1 + rn - 1 知 d = rn - 3 - hn - 1rn - 2. 利用前面推導方式我們知存在 m1,m2,n1,n2 使得 rn - 3 = m1a + n1b 且 rn - 2 = m2a + n2b 故代入得

import Foundation

func gcd(a: Int, b: Int) -> Int {
    var x = a, y = b
    while y != 0 {
        (x, y) = (y, x % y)
    }
    return x
}


let x = 75, y = 100
let result = gcd(a: x, b: y)
print("\(x) 和 \(y) 的最大公約數是 \(result)")

package main
import "fmt"
func main() {
    var x, y int = 18, 12 
    result := gcd(x,y)  
    fmt.Printf("x, y 的最大公約數是 : %d",result)
}
func gcd(x,y int) int{
     for y != 0  {     
            x, y = y, x%y 
      }  
    return x
}

var  a,b,c:integer;
begin
  readln(a,b);
  c:=a mod b;
  while c<>0 do
  begin
    a:=b;b:=c;c:=a mod b;
  end;
  write(b);
end.

/*
歐幾里得算法：輾轉求餘
原理： gcd(a,b)=gcd(b,a mod b)
當b為0時，兩數的最大公約數即為a
getchar()會接受前一個scanf的回車符
*/
#include<stdio.h>
  
unsigned int MaxCommonFactor(int a,int b)
{
	if(a % b == 0)
    	return b;
  	return MaxCommonFactor(b, a % b);
}
  
unsigned int Gcd(unsigned int M,unsigned int N)
{
	unsigned int Rem;
	while(N > 0)
	{
		Rem = M % N;
        M = N;
		N = Rem;
	}
	return M;
}

int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	printf("the greatest common factor of %d and %d is ",a,b);
    printf("%d\n",Gcd(a,b));
  	printf("recursion:%d\n",MaxCommonFactor(a,b));
	return 0;
}

#用歐幾里得算法計算最大公約數(排版略）
def gcd(x, y)
if y == 0
return x
else
return gcd(y, x % y)
end
end

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    if (a % b==0) return b;
    else return gcd(b, a % b);
}
int x, y; 
int main(){
	
	cin >> x >> y;
	cout << gcd(x, y);
	
	return 0;
}

int gcd(int m,int n)
{   if(n == 0){
        return m; 
    }
    int r = m%n;
    return gcd(n,r);
}

 function gcd(a, b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }

def gcd(a, b):
    while a != 0:
        a, b = b % a, a

    return b
　

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

 pub fn gcd(x: u64, y: u64) -> u64 {    
   let remainder = x % y;    

   if remainder == 0 {    
       return y;    
   } else {    
       return gcd(y, remainder);    
   }    
}    

#[cfg(test)]    
mod tests {    
use super::*;    

#[test]    
fn gcd_works() {    
assert_eq!(gcd(2, 4), 2);    
       assert_eq!(gcd(6, 27), 3);    
assert_eq!(gcd(4, 2), 2);    
assert_eq!(gcd(27, 6), 3);    
   }    
}

function gcd() {
	if [ ! -n "$2" ];then
		return
	fi
	if [ "$2" == "0" ];then
		echo "$1"
		return
	fi
	gcd "$2" "$[$1%$2]"
}

euclid :: Int -> Int -> Int
euclid x y
    | x <= 0 || y <= 0 = error "euclid: non-positive integer in input"
    | x == y = x
    | x <  y = euclid x (y - x)
    | x >  y = euclid (x - y) y

#include <stdio.h>
unsigned int gcdExtended( int a,  int b,  int *x,  int *y);
int main(void) {

    int  a, b,GCD;
    int   x, y;

    a = 1232, b = 573;

    /*
    gcdExtended(1232, 573)時, x = 20 and y = –43
    1232x + 573y = 1
    24640-24639 = 1
    或者gcdExtended( 573,1232) 時,x=-43, y=20
    573x+1232y = 1
    -43*573+1232*20 = -24639+57640 = 1

    gcdExtended(9151, 5787) 時
    x=2011, y=-3180

     */
    GCD =  gcdExtended(a, b,&x, &y);
    printf("gcdExtended(%d, %d) = %d, x=%d, y=%d\n", a, b, GCD,x,y);

    return 0;
}

// 歐幾里得擴展算法的C語言實現
// ax+by=1
unsigned int gcdExtended(int a, int b, int *x, int *y){

    if (a == 0){
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = gcdExtended(b%a, a, &x1, &y1);

    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}

參考資料

• 1.    Grossman JW. Discrete Mathematics. New York: Macmillan. 1990: 213. ISBN 0-02-348331-8.
• 2.    Ross Honsberger．Mathematical Gems II．The United States of America：The Mathematical Association of America，1997-9-11：54-57