若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里德算

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 10:04:37
若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里德算若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里

若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里德算
若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里德算

若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里德算
辗转相除法
开放分类:数学、最大公约数
辗转相除法,又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法.它是已知最古老的算法,其可追溯至前300年.它首次出现于欧几里德的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》.它并不需要把二数作质因子分解.
证明:
设两数为a、b(b<a),求它们最大公约数(a、b)的步骤如下:用b除a,得a=bq?1+r?1(0≤r?1<b).若r?1=0,则(a,b)=b;若r?1≠0,则再用r?1除b,得b=r?1q?2+r?2(0≤r?2<r?1).若r?2=0,则(a,b)=r?1,若r?2≠0,则继续用r?2除r?1,……如此下去,直到能整除为止.其最后一个非零余数即为(a,b).
[编辑] 算法
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:
1.若 r 是 a ÷ b 的余数,则
gcd(a,b) = gcd(b,r)
2.a 和其倍数之最大公因子为 a.
另一种写法是:
1.a ÷ b,令r为所得余数(0≤r<b)
若 r = 0,算法结束;b 即为答案.
2.互换:置 a←b,b←r,并返回第一步.
[编辑] 虚拟码
这个算法可以用递归写成如下:
function gcd(a,b) {
if a mod b0
return gcd(b,a mod b);
else
return a;
}
或纯使用循环:
function gcd(a,b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
其中“a mod b”是指取 a ÷ b 的余数.
例如,123456 和 7890 的最大公因子是 6,这可由下列步骤看出:
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0
只要可计算余数都可用辗转相除法来求最大公因子.这包括多项式、复整数及所有欧几里德定义域(Euclidean domain).
辗转相除法的运算速度为 O(n2),其中 n 为输入数值的位数.

辗转相除法
辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出现于欧几里德的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
证明:
设两数为a、b(b<a),求它们最大公约数(a、b)...

全部展开

辗转相除法
辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出现于欧几里德的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
证明:
设两数为a、b(b<a),求它们最大公约数(a、b)的步骤如下:用b除a,得a=bq......r 1(0≤r)。若r1=0,则(a,b)=b;若r1≠0,则再用r1除b,得b=r1q......r2 (0≤r2).若r2=0,则(a,b)=r1,若r2≠0,则继续用r2除r1,……如此下去,直到能整除为止。其最后一个非零余数即为(a,b)。
[编辑] 算法
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:
1. 若 r 是 a ÷ b 的余数, 则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是:
1. a ÷ b,令r为所得余数(0≤r<b)
若 r = 0,算法结束;b 即为答案。
2. 互换:置 a←b,b←r,并返回第一步。

收起

辗转相除法

若给定两个正整数m和n,试写出求他们的最大公因子(既能够同时整除m和n的最大整数)的算法——欧几里德算 在等差数列an中,对于给定的正整数n和正整数M,若同时满足a1 各位大神,帮帮忙,计算组合数给定两个正整数n和m(m 求两个正整数m和n的最大公约数 写出两个正整数m,n m 描述:求对于给定的正整数n(1 最大公约数 c语言 紧急~`给定两个正整数,求它们的最大公约数.关于输入 输入的第一个整数为 n ,其后 n 行每行两个正整数( 输入两个正整数M和N求最小公倍数 C程序 输入两个正整数m和n(m 输入两个正整数m和n,求它们的最大公约数和最小公倍数.(习题6.1) 设n为给定的正整数,设An={x丨2^n < x < 2^n+1,且x=3m,m∈N}.设n为给定的正整数,设An={x丨2^n < x < 2^n+1,且x=3m,m∈N}.(1)当n为奇数时,求An中的最大值和最小值.(2)求An中所有元素之和. c语言,输入两个正整数m和n,求两个数的最大公约数与最小公倍数 c语言编写程序用辗转相除法求两个正整数m和n的最大公约数 编写一个函数功能是求两个正整数m和n的最大公约数 C语言 编写函数:输入两个正整数m,n,求它们的最大公约数和最小公倍数 编写函数:输入两个正整数m,n,求它们的最大公约数和最小公... c语言 求两个正整数m,n的最小公倍数 m、n两个整数,若n整除m.记作n!m,已知正整数a满足192!(a 立方+191,a小于2009求满足条件的所有可能的正整数a的和