Как найти 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, а также Жг = |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)));
}

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

• рассчитал GCD функционально
• Используется синтаксис 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();
}

GCD:

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

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

Answer 8

для 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 9

В основном, чтобы найти 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));
    }
}

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

Answer 10

Импорт 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 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

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 13

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

Здесь сначала для цикла предназначена для получения всех чисел, начиная с «2». Тогда, если утверждение проверьте, разделяет ли номер (I) LCM, если он пропускает, то он пропускает, что нет. И если он не будет рядом с циклом для поиска нет. Что может разделить число (i), если это произойдет, нам не нужно, что нет. Мы хотим только его дополнительный фактор. Итак, здесь, если флаг правда, это означает, что уже имели некоторые факторы нет. «Я в LCM. Поэтому мы разделяем это факторы и умножьте дополнительный фактор на LCM. Если номер не делится по любому из его предыдущих нет. Затем, когда просто умножьте его на LCM.