كيفية العثور على 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 (وتريد بالفعل) ، فيمكنك استخدام تعبيرات 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)));
}

لقد وجهت نفسي إجابة جيفري هانتين, ، لكن

• حساب GCD وظيفيا
• استخدمت Varargs-Syntax للحصول على واجهة برمجة تطبيقات أسهل (لم أكن متأكدًا مما إذا كان الحمل الزائد سيعمل بشكل صحيح ، لكنه يعمل على جهازك)
• حولت GCD من numbers-Ray في بناء جملة وظيفية ، وهو أكثر إحكاما وأسهل القراءة (على الأقل إذا كنت تستخدم للبرمجة الوظيفية)

ربما يكون هذا النهج أبطأ قليلاً بسبب مكالمات الوظائف الإضافية ، لكن هذا ربما لن يهم على الإطلاق لحالات الاستخدام.

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 ، يمكنك استخدام خوارزمية Euclid للعثور على 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;
        }

هنا ، أولاً بالنسبة إلى Loop للحصول على كل الأرقام تبدأ من "2". ثم إذا تحقق من أن الرقم (i) يقسم LCM إذا كان ذلك ، فسيخطي ذلك. وإذا لم يكن الأمر كذلك ، فإن الحلقة التالية هي العثور على لا. الذي يمكن أن يقسم الرقم (i) إذا حدث هذا ، فلن بحاجة إلى ذلك. نريد فقط عاملها الإضافي. لذا ، إذا كان العلم صحيحًا ، فهذا يعني أن هناك بالفعل بعض عوامل لا. "أنا" في LCM. لذلك نحن نقسم هذه العوامل ونضاعف العامل الإضافي إلى LCM. إذا لم يكن الرقم غير قابل للقسمة بأي من لا. ثم عندما تضربه ببساطة إلى LCM.