如何在一組數字上找到GCD，LCM

Question

對一組數字計算最大公約數和最小公倍數，最簡單的方法是什麼？什麼數學函數可以用來找到這些信息？

Answer 1

我用Euclid's algorithm找到最大的普通di兩個數字的遮陽板;它可以迭代以獲得更大數字集合的GCD。

private static long gcd(long a, long b) 
{ 
    while (b > 0) 
    { 
     long temp = b; 
     b = a % b; // % is remainder 
     a = temp; 
    } 
    return a; 
} 

private static long gcd(long[] input) 
{ 
    long result = input[0]; 
    for(int i = 1; i < input.length; i++) result = gcd(result, input[i]); 
    return result; 
} 

最小公倍數是有點麻煩，但可能是最好的辦法是reduction by the GCD，可同樣迭代：

private static long lcm(long a, long b) 
{ 
    return a * (b/gcd(a, b)); 
} 

private static long lcm(long[] input) 
{ 
    long result = input[0]; 
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]); 
    return result; 
} 

Answer 2

它沒有構建它的功能。您可以使用Euclid's algorithm找到兩個數字的GCD。

對於一組數

的

GCD(a_1,a_2,a_3,...,a_n) = GCD(GCD(a_1, a_2), a_3, a_4,..., a_n) 

應用它遞歸。

同樣爲LCM：

LCM(a,b) = a * b/GCD(a,b) 
LCM(a_1,a_2,a_3,...,a_n) = LCM(LCM(a_1, a_2), a_3, a_4,..., a_n) 

Answer 3

沒有爲GCD一個Euclid's algorithm，

public int GCF(int a, int b) { 
    if (b == 0) return a; 
    else return (GCF (b, a % b)); 
} 

順便提一下，a和b應該大於或等於0，和LCM = |ab|/GCF(a, b)

Answer 4

int lcmcal(int i,int y) 
{ 
    int n,x,s=1,t=1; 
    for(n=1;;n++) 
    { 
     s=i*n; 
     for(x=1;t<s;x++) 
     { 
      t=y*x; 
     } 
     if(s==t) 
      break; 
    } 
    return(s); 
} 

Answer 5

int lcm(int x,int y){ 

    int i=1;  

    while(true){ 

     if(!(x*i)%y) 
      return x*i; 

     i++; 
    } 

Answer 6

int gcf(int a, int b) 
{ 
    while (a != b) // while the two numbers are not equal... 
    { 
     // ...subtract the smaller one from the larger one 

     if (a > b) a -= b; // if a is larger than b, subtract b from a 
     else b -= a; // if b is larger than a, subtract a from b 
    } 

    return a; // or return b, a will be equal to b either way 
} 

int lcm(int a, int b) 
{ 
    // the lcm is simply (a * b) divided by the gcf of the two 

    return (a * b)/gcf(a, b); 
} 

Answer 7

更容易理解：

{ int num1,num2; 
    int m1,m2,r; 
    cout<<"Enter two numbers: "<<endl; 
    cin>>num1>>num2; 
    if(num1>num2) 
    { 
    m1=num1; 
    m2=num2; 
    } 
    else 
    { 
    m1=num2; 
    m2=num1; 
    } 
    while(r!=0) 
    { r=m1%m2; m1=m2; m2=r; 
    } 
    cout<<"result of gcd of two number is "<<m1<<endl; 
    int lcm= (num1*num2)/m1; 
    cout<<"result of lcm of two number is "<<lcm; 
    } 

- 查看更多的部位：http://www.easycppcodes.com/2015/01/find-gcd-and-lcm-of-two-numbers-using.html#sthash.lAWwqgS5.dpuf

Answer 8

import java.util.Scanner; 公共類Lcmhcf {

/** 
* @param args the command line arguments 
*/ 
public static void main(String[] args) { 
    // TODO code application logic here 
    Scanner scan = new Scanner(System.in); 
    int n1,n2,x,y,lcm,hcf; 
    System.out.println("Enter any 2 numbers...."); 
    n1=scan.nextInt(); 
    n2=scan.nextInt(); 
    x=n1; 
    y=n2; 

    do{ 
     if(n1>n2){ 
     n1=n1-n2; 
     } 
     else{ 
     n2=n2-n1; 
     } 
    } while(n1!=n2); 
    hcf=n1; 
    lcm=x*y/hcf; 
    System.out.println("HCF IS = "+hcf); 
    System.out.println("LCM IS = "+lcm); 

    } 
} 
//## Heading ##By Rajeev Lochan Sen 

Answer 9

在Java 8中，有更優雅和功能的方式來解決這個問題。

LCM：

private static int lcm(int numberOne, int numberTwo) { 
    final int bigger = Math.max(numberOne, numberTwo); 
    final int smaller = Math.min(numberOne, numberTwo); 

    return IntStream.rangeClosed(1,smaller) 
        .filter(factor -> (factor * bigger) % smaller == 0) 
        .map(factor -> Math.abs(factor * bigger)) 
        .findFirst() 
        .getAsInt(); 
} 

GCD：

private static int gcd(int numberOne, int numberTwo) { 
    return (numberTwo == 0) ? numberOne : gcd(numberTwo, numberOne % numberTwo); 
} 

當然，如果一個參數爲0，這兩種方法是行不通的。

Answer 10

如果你可以使用Java 8（實際上是希望），你可以使用lambda表達式在功能上解決這個問題：

private static int gcd(int x, int y) { 
    return (y == 0) ? x : gcd(y, x % y); 
} 

public static int gcd(int... numbers) { 
    return Arrays.stream(numbers).reduce(0, (x, y) -> gcd(x, y)); 
} 

public static int lcm(int... numbers) { 
    return Arrays.stream(numbers).reduce(1, (x, y) -> x * (y/gcd(x, y))); 
} 

我面向自己的Jeffrey Hantin's answer，但

• 計算GCD功能
• 使用varargs-Syntax獲得更簡單的API（我不確定過載是否能正常工作，但它確實在我的機器上）
• 轉化的numbers - 陣列的GCD到功能語法，這是更緊湊，更容易IMO閱讀（至少如果你使用函數式編程）

這種方法可能是稍微慢一些，由於額外的函數調用，但對於大多數用例來說，這可能根本就不重要。

Answer 11

import java.util.Scanner; 
public class Main { 
    public static void main(String[] args) { 
     Scanner input = new Scanner(System.in); 
     int n0 = input.nextInt(); // number of intended input. 
     int [] MyList = new int [n0]; 

     for (int i = 0; i < n0; i++) 
      MyList[i] = input.nextInt(); 
      //input values stored in an array 
     int i = 0; 
     int count = 0; 
      int gcd = 1; // Initial gcd is 1 
      int k = 2; // Possible gcd 
      while (k <= MyList[i] && k <= MyList[i]) { 
       if (MyList[i] % k == 0 && MyList[i] % k == 0) 
        gcd = k; // Update gcd 
       k++; 
       count++; //checking array for gcd 
      } 
      // int i = 0; 
      MyList [i] = gcd; 
      for (int e: MyList) { 
       System.out.println(e); 

      } 

      } 

     } 

Answer 12

int main() 
{ 
    int n1,n2,num1,num2,rem,gcd,lcm; 
    printf("Enter a number:"); 
    scanf("%d %d",&num1,&num2); 
    num1=n1; 
    num2=n2; 
    while(num2!=0) 
    { 
     rem=num1%num2; 
     num1=num2; 
     num2=rem; 
    } 
    gcd=num1; 
    lcm=(n1*n2)/gcd; 
    printf("Gcd=%d\n",gcd); 
    printf("Lcm=%d\n",lcm); 
} 

Answer 13

//找到兩個號碼[非常簡單的方法]

類LCM

{

static void main(int n1,int n2) 

{ 




    int lcm; 




    int a=n1; 

    int b=n2; 

    System.out.println("\f"); 


    if(n1==0||n2==0) 
    { 
     System.out.println("enter different number"); 
    } 

    else 
    { 
     while(a!=b) 
     { 
      if(a>b) 
      { 
       a=a-b; 
      } 

      else 
      { 
       b=b-a; 
      } 
     } 

    int GCD=a; 

    lcm=(n1*n2)/GCD; 

    System.out.println("the LCM is "+lcm); 
    } 

}}

那就是LCM一個非常簡單的方法OD ... [嘗試自己理解的Cuz編碼方式理解... :)]

Answer 14

爲gcd你CAD如下操作：

String[] ss = new Scanner(System.in).nextLine().split("\\s+"); 
    BigInteger bi,bi2 = null; 
    bi2 = new BigInteger(ss[1]); 
    for(int i = 0 ; i<ss.length-1 ; i+=2) 
    { 
     bi = new BigInteger(ss[i]); 
     bi2 = bi.gcd(bi2); 
    } 
    System.out.println(bi2.toString()); 

Answer 15

基本上找到最大公約數和最小公倍數的一組數字可以用下面的公式，

LCM(a, b) X HCF(a, b) = a * b 

與此同時，在Java中，你可以使用Euclid算法找到最大公約數和最小公倍數，這樣

public static int GCF(int a, int b) 
{ 
    if (b == 0) 
    { 
     return a; 
    } 
    else 
    { 
     return (GCF(b, a % b)); 
    } 
} 

你可以參考this資源找到關於歐幾里得算法的例子。