欧几里得GCD算法
GCD：Greatest Common Divisor 最大公约数问题。
算法的伪代码表示
◼初始条件： ◼给定整数𝒂 ≥ 𝟎,𝒃 ≥ 𝟎，且𝒂,𝒃不同时为0； ◼ 目标：求𝒂,𝒃的最大公约数。 ◼ 方法： 1. 输入𝒂,𝒃 2. while 𝒃 ≠ 𝟎 3. r = a MOD b 4. a = b 5. b = r 6. 转2 7. 输出结果：a
算法的手算表格
求1035与759的最大公约数
算法的java代码表示
package e
;
import java
.util
.*
;
public class GCD {
static Scanner input
= new Scanner(System
.in
);
public static void main(String
[] args
) {
System
.out
.println("请输入第一个数字a：");
int a
= input
.nextInt();
System
.out
.println("请输入第二个数字b：");
int b
= input
.nextInt();
EuclidGCD(a
, b
);
}
public static void EuclidGCD(int a
,int b
){
int r
= 0;
int q
= 0;
System
.out
.println("a b r q");
while(b
!= 0) {
r
= a
% b
;
q
= a
/ b
;
System
.out
.println(" "+a
+" "+b
+" "+r
+" "+q
);
a
= b
;
b
= r
;
}
System
.out
.println(" "+a
+" "+b
);
}
}
java代码运行结果
