Как найти GCD, LCM по набору номеров

Question

Какой самый простой способ вычислить Величайший общий делитель и Наименьшее общее кратное для набора чисел?Какие математические функции можно использовать для поиска этой информации?

Answer 1

Я использовал алгоритм Евклида , чтобы найти наибольший общий делитель двух чисел;его можно повторить, чтобы получить 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 gcd(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}

Answer 2

Существует алгоритм Евклида для GCD,

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 3

Нет встроенной функции для него.Вы можете найти 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 4

Если вы можете использовать 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)));
}

Я ориентировался на Ответ Джеффри Хантина , но

• рассчитал ЖКД функционально
• использовал синтаксис varargs для более простого API (я не был уверен, будет ли корректно работать перегрузка, но это работает на моей машине)
• преобразовал gcd numbers -Array в функциональный синтаксис, который стал более компактным и более легким для чтения IMO (по крайней мере, если вы привыкли к функциональному программированию)

Этот подход, вероятно, немного медленнее из-за дополнительных вызовов функций, но это, вероятно, не будет иметь значения вообще для большинства случаев использования.

Answer 5

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 6

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 7

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

НОД:

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

Конечно, если один аргумент равен 0, оба метода не будут работать.

Answer 8

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, если это так, то он пропускает это нет и если это не так, то следующий цикл for для поиска нет. который может делить число (I), если это произойдет, нам не нужно, что нет. нам нужен только дополнительный фактор. так что здесь, если флаг имеет значение true, это означает, что там уже были некоторые факторы нет. «Я» в lcm. поэтому мы делим эти факторы и умножаем дополнительный коэффициент на lcm. Если число не делится ни на один из его предыдущих нет. затем, когда просто умножить его на lcm.

Answer 9

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

Answer 10

В основном, чтобы найти gcd и lcm по набору чисел, вы можете использовать следующую формулу:

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

Между тем в java вы можете использовать алгоритм euclid для поиска gcd и lcm, например:

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

Вы можете обратиться к этому ресурсу, чтобы найти примеры алгоритма Евклида.