lcd.java

来自「java 实现的一些算法： 赛选法求素数」· Java 代码 · 共 25 行

package daniel.number_theory;

/**
 * 欧几里德算法；辗转相除法。
 * 
 * 如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,
 * 如果 a 是m，n的最大公约数，所以m，n可以被a整除。又因为 有等是m=nq+r；所以a也可以整除r；
 * @author MIMO
 *
 */
public class LCD {
	
	public static int lcd(int a,int b){
		if(b == 0){
			return a;
		}
		return lcd(b,a % b);
	}
	
	public static void main(String [] args){
		System.out.println(lcd(11,20));
		System.out.println(10%20);
	}
}