欧几里得算法实现与最大公约数算法研究

2018-03-27

欧几里德算法形式很简单,形式与证明都十分的容易,但是却广泛的应用在各个科学领域的边角,这里对其进行证明与语言实现版本给出。

核心算法:

数学证明:

,则有;

再设,公约数,则有:,

由于,则有,故的公约数。

的一任意公约数,则有,.

.故公约数。

高级语言实现

int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int gcd(int a,int b){
    int t;
    while(t){
        t=a%b;
        a=b;
        b=t;
    }
    return a;
}

相关算法还有,扩展欧几里得算法,Stein算法等,以后慢慢写。

算法不是最后的图穷匕见,数学上构造的纯理性过程,才是Real Hard Core.

世之奇伟、瑰怪、非常之观,常在险远,而人之所罕至焉.故非有志者不能至。

如是也。

回到首页

所有文章