辗转相除法

今天回顾一下以前学过的C++,看到了用辗转相除法求两个正整数的最大公约数,似乎很有意思,记录下来,以后忘记的时候可以看看。

for ((r = m % n) != 0) {
	m = n;
	n = r;
}
/* n is the Greatest Common Divisor of m and n */

上面举了一个C代码的例子。然后上网查了一下为什么这样辗转相除可以得到最大公约数。其实就是要搞清为什么gcd(m, n)和gcd(n, r)是一样的。

假设“m = n × q + r”,再假设x是m和n的公约数,则x能够整除m,也能够整除n,因此x能够整除r。因为m和n的任意公约数x都有刚才说的性质,就是能够整除r。所以,最大公约数作为公约数的一个也不例外,最大公约数也能整除r,所以gcd(m, n)和gcd(n, r)相等。

这篇日志的另外一个目的是试验一下Syntax Highlight这个插件,用来把代码上色的,效果不错。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s