最大公約數環

我正在做一些自學成才的Java，但似乎無法找出問題在這個循環：最大公約數環

的問題是找到兩個整數n1和n2最大公約數其中d是較小的值。該方法是遞減d，直到一個GCD或達到1 ...以下是我在哪裏至今：

Scanner input = new Scanner(System.in); 
    System.out.println("Please enter two integers: "); 
    int n1 = input.nextInt(); 
    int n2 = input.nextInt(); 

    int d = 0; 
    int temp = 0; 
    //finds the lowest value 
    if(n1 < n2) { 
     temp = n1; 
     n1 = n2; 
     n2 = temp; 
    } 

    for(d = n1;(n1 % d !=0 && n2 % d != 0);d--) { 

    } 

    System.out.println("The GCD of " + n1 + " and " + n2 + " is " + d);

任何指針？

來源

2013-05-07 mikedugan

這不是你的問題，但你可以用兩個較小的開始，因爲GCD永遠不會大於較小的輸入。 – cmd 2013-05-07 16:17:28

在這裏的邏輯是錯誤的：

(n1 % d !=0 && n2 % d != 0)

變化：

3210

或者代碼將停止一次是看到N1 或 N2的除數，而不是他們的GCD，因爲循環終止條件應該是你想要做的事情的否定。

來源

2013-05-07 16:13:27

少女時代！謝謝 – mikedugan 2013-05-07 16:18:50

什麼做這樣的：

for(d = n1; d > 1; d--) { 
    if(n1%d == 0 && n2%d == 0) 
     break; 
}

來源

2013-05-07 16:19:21 sha1

當它達到循環連續條件時它會自動中斷 – mikedugan 2013-05-07 16:41:50

你的意思是，在'd> 1'部分？ – sha1 2013-05-07 17:18:56

我測試了一些輸入，但我在這裏看不到任何問題。 – sha1 2013-05-07 17:29:44

公共靜態INT GCD（INT A，INT B）

{ 
    if(a>b) 
     if(a%b==0) 
      return b; 
     else 
      return gcd(b,a%b); 
    else 
     if(b%a==0) 
      return a; 
     else 
      return gcd(a,b%a); 
}

這是一個沒有遍歷所有的數字是最好的方法。試着自己理解，這將有助於你開發邏輯，如果你不能理解回覆我，我會解釋邏輯。

來源

2013-05-07 16:38:47

這個循環基本上在一行中完成了這一切:) – mikedugan 2013-05-07 16:41:07

當兩個數字非常大，例如197853,54689只要想象一下你將需要的循環數量，而這會在更短的時間內發生。：d – 2013-05-07 16:44:21

該問題也可以用不同的方式解決。下面的代碼不是我的，但我已經很好地理解了的邏輯。你的邏輯是好的，正如答案所表明的那樣，它現在也是完美無瑕的。我給你的建議是嘗試爲這樣的計算寫一個函數。如果這樣做，你可以用一種非常簡單的方式做很好的工作。下面的代碼是寫函數有用的一個很好的例子。

public static int gcd(int a,int b){ 
    if(b==0){ 
     return a; 
    } 
     return gcd(b,a%b);   
} 
public static void main(String args[]){ 
    Scanner input = new Scanner(System.in); 
    System.out.println("Please enter two integers: "); 
    int n1 = input.nextInt(); 
    int n2 = input.nextInt(); 
    System.out.println("The GCD of " + n1 + " and " + n2 + " is " + gcd(n1,n2)); 

}

一切順利！

來源

2013-08-04 18:16:32 Deepeshkumar

迭代

public static long gcd(long a, long b){ 
    long factor= Math.max(a, b); 
    for(long loop= factor;loop > 1;loop--){ 
     if(a % loop == 0 && b % loop == 0){ 
     return loop; 
     } 
    } 
    return 1; 
}

迭代歐幾里德的算法

public static int gcd(int a, int b) //valid for positive integers. 
{ 
    while(b > 0) 
    { 
     int c = a % b; 
     a = b; 
     b = c; 
    } 
    return a; 
}

優化迭代

static int gcd(int a,int b) 
    { 
     int min=a>b?b:a,max=a+b-min, div=min; 
     for(int i=1;i<min;div=min/++i) 
      if(max%div==0) 
       return div; 
     return 1; 
    }

遞歸

public static long gcd(long a, long b){ 
    if(a == 0) return b; 
    if(b == 0) return a; 
    if(a > b) return gcd(b, a % b); 
    return gcd(a, b % a); 
}

通過內置

import java.math.BigInteger; 

public static long gcd(long a, long b){ 
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue(); 
}

- http://rosettacode.org/wiki/Greatest_common_divisor

來源

2013-10-20 01:51:32

最大公約數環

回答

相關問題