71

一連の数値で最大公約数と最小公倍数を計算する最も簡単な方法は何でしょうか。この情報を見つけるために使用できる数学関数は何ですか？

4

14 に答える 14

147

私はユークリッドのアルゴリズムを使用して、2つの数値の最大公約数を見つけました。より大きな数のセットの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;
}

最小公倍数は少しトリッキーですが、おそらく最良のアプローチは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;
}
于 2010-11-17T06:44:21.850 に答える
25

GCDにはユークリッドの互除法があります。

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

ちなみに、、以上aである必要があり、LCM =b0|ab| / GCF(a, b)

于 2010-11-17T06:29:16.420 に答える
14

そのための組み込み関数はありません。ユークリッドのアルゴリズムを使用して、2つの数値の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 )
于 2010-11-17T06:28:53.020 に答える
10

Java 8を使用できる（そして実際に使用したい）場合は、ラムダ式を使用してこれを機能的に解決できます。

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)));
}

私はジェフリー・ハンティンの答えに自分自身を向けましたが、

  • gcdを機能的に計算しました
  • より簡単なAPIのためにvarargs-Syntaxを使用しました（オーバーロードが正しく機能するかどうかはわかりませんでしたが、私のマシンでは機能します）
  • -Arrayのgcdnumbersを関数型構文に変換しました。これは、よりコンパクトでIMOが読みやすくなっています（少なくとも関数型プログラミングに慣れている場合）。

このアプローチは、追加の関数呼び出しのためにおそらく少し遅くなりますが、ほとんどのユースケースではおそらくまったく問題になりません。

于 2016-11-10T15:27:14.060 に答える
4 
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);
}
于 2014-08-17T09:21:01.657 に答える
2 
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);
}
于 2011-07-13T18:06:51.753 に答える
1

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の場合、両方の方法は機能しません。

于 2016-05-10T15:42:30.300 に答える
0

あなたのため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());
于 2018-02-07T16:37:51.830 に答える
0

基本的に、以下の式を使用できる一連の数値でgcdとlcmを見つけるには、

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

一方、Javaでは、ユークリッドのアルゴリズムを使用して、次のようにgcdとlcmを見つけることができます。

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

このリソースを参照して、ユークリッドのアルゴリズムの例を見つけることができます。

于 2018-03-01T12:15:34.073 に答える
0 
public class HcfLcm {
    public static void main(String[] args) {
        System.out.println("HCF: "+ getHcf(20, 15)); //5
        System.out.println("LCM: "+ getLcm2(20, 15)); //60
    }

    private static Integer getLcm2(int n1, int n2) {
        int lcm = Math.max(n1, n2);
        // Always true
        while (true) {
            if (lcm % n1 == 0 && lcm % n2 == 0) {
                break;
            }
            ++lcm;
        }
        return lcm;
    }

    private static Integer getLcm(int i, int j) {
        int hcf = getHcf(i, j);
        return hcf * i/hcf * j/hcf; // i*j*hcf
    }

    private static Integer getHcf(int i, int j) {
        while(i%j != 0) {
            int temp = i%j;
            i = j;
            j = temp;
        }
        return j;
    }
}
于 2020-07-25T22:04:01.530 に答える
-1

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
于 2016-04-15T12:06:01.827 に答える
-1 
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);

            }

            }

        }
于 2016-11-24T04:22:27.510 に答える
-1 
import java.util.*;
public class lcm {
    public static void main(String args[])
    {
        int lcmresult=1;
        System.out.println("Enter the number1: ");
        Scanner s=new Scanner(System.in);
        int a=s.nextInt();
        System.out.println("Enter the number2: ");
        int b=s.nextInt();
        int max=a>b?a:b;
        for(int i=2;i<=max;i++)
        {
            while(a%i==0||b%i==0)
            {
                lcmresult=lcmresult*i;
                if(a%i==0)
                    a=a/i;
                if(b%i==0)
                    b=b/i;
                if(a==1&&b==1)
                    break;
            }
        }
    System.out.println("lcm: "+lcmresult);
}
}
于 2018-04-01T18:33:18.873 に答える
-1 
int lcm = 1;
int y = 0;
boolean flag = false;
for(int i=2;i<=n;i++){
            if(lcm%i!=0){
                for(int j=i-1;j>1;j--){
                    if(i%j==0){
                        flag =true;
                        y = j;
                        break;
                    }
                }
                if(flag){
                    lcm = lcm*i/y;
                }
                else{
                    lcm = lcm*i;
                }
            }
            flag = false;
        }

ここで、最初のforループは、「2」から始まるすべての数値を取得するためのものです。次に、ステートメントが数値（i）がlcmを除算するかどうかをチェックし、除算する場合は、そのnoをスキップします。そうでない場合、次のforループはnoを見つけるためのものです。これが発生した場合、数値（i）を除算できますが、その必要はありません。余分な要素だけが必要です。したがって、ここでフラグが真の場合、これはすでにいくつかの要因がないことを意味します。lcmの「i」。したがって、その因数を除算し、余分な因数をlcmに乗算します。番号が以前の番号のいずれかで割り切れない場合。次に、単純に最小公倍数に乗算します。

于 2018-07-22T02:22:34.333 に答える