“歐幾里得算法：歐幾里德算法又稱輾轉(zhuǎn)相除法访得，是指用于計算兩個正整數(shù)a，b的最大公約數(shù)访娶。應(yīng)用領(lǐng)域有數(shù)學(xué)和計算機(jī)兩個方面又固。計算公式gcd(a,b) = gcd(b,a mod b)⌒虢蹋”——百度百科
【注意皿渗，公式是gcd(a,b)=gcd(b,a mod b)，不能是gcd(a,b)=gcd(a mod b,b)轻腺。否則會出問題乐疆。】
gcd.java:
package zdy.com.company;
public class gcd {
//計算兩個非負(fù)整數(shù)p和q的最大公約數(shù)：
// 若q是0贬养，則最大公約數(shù)為p挤土。
// 否則，將p除以q得到余數(shù)r误算，p和q的最大公約數(shù)即為q和r的最大公約數(shù)耕挨。
public static int gcd(int p,int q){
if(q==0)return p;
int r = p % q;
return gcd(q,r);
}
}
【在這里细卧，如果公式是gcd(a,b)=gcd(a mod b,b)，即q≠0時return的是gcd（r,q）,當(dāng)傳入的p=6筒占，q=33時贪庙，會陷入死循環(huán)『采唬】
Main.java:
package zdy.com.company;
import java.awt.*;
public class Main
{
public static void main(String args[]){
int i=0;
i=gcd.gcd(6,33);//調(diào)用歐幾里得算法計算6和33的公約數(shù)
System.out.print(i);
}
}
運(yùn)行結(jié)果
運(yùn)行結(jié)果.png
