注:本文为《算法(第4版)》的读书笔记。

算法描述:

计算两个非负整数p和q的最大公约数:若q是0,则最大公约数为p。否则,将p除以q得到余数r, p和q的最大公约数即为q和r的最大公约数。

java语言描述:

    public static int gcd(int p, int q){
	if(q == 0){
            return p;
	}
	int r = p % q;
	return gcd(q, r);
    }

 

测试程序:

import java.util.Scanner;
import java.io.*;
public class GCD
{
    public static int gcd(int p, int q){
	if(q == 0){
            return p;
	}
	int r = p % q;
	return gcd(q, r);
    }
    public static void main(String[] args)  throws Exception{
        int a,b;
	InputStream is = System.in;
	Scanner scan = new Scanner(is);
	System.out.println("请输入第一个数字后按回车确认");
	a = scan.nextInt();
	System.out.println("请输入第二个数字后按回车确认");
	b = scan.nextInt();
	int x = GCD.gcd(a, b);
	System.out.println("最大公约数是:" + x);
    }
}