С# найти наибольший общий делитель

"Наибольший общий делитель двух целых чисел - это наибольшее целое число, которое равномерно делит каждое из двух чисел. Напишите метод Gcd, который возвращает наибольший общий делитель двух целых чисел. Включите метод в приложение, которое считывает два значения от пользователя и отображает результат. "

(это не домашняя работа, а упражнение в книге, которую я использую)

Вы можете помочь мне решить это? Вот что у меня так далеко.

(изменить - я могу отправить два числа, но GCD для меня не рассчитается)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Greatest_Common_Divisor
{
class Program
{

    static int GetNum(string text)
    {
        bool IsItANumber = false;
        int x = 0;
        Console.WriteLine(text);

        do
        {
            IsItANumber = int.TryParse(Console.ReadLine(), out x);

        } while (!IsItANumber);

        return x;
    }
    static void Main(string[] args)
    {
        string text = "enter a number";
        int x = GetNum(text);
        text = "enter a second number";
        int y = GetNum(text);


        int z = GCD(x, y);
        Console.WriteLine(z);
    }

    private static int GCD(int x, int y)
    {
        int v = 0;
        int n = 0;

        v = GetGreatestDivisor(x, y);


        return v;

    }

    static int GetGreatestDivisor(int m, int h)
        {

            do
            {
                for (int i = m; i <= 1; i--)



                    if (m%i == 0 && h%i == 0)
                    {
                        int x = 0;
                        x = i;

                        return x;
                    }
            } while (true);
            return m;
        }

  }
}

Ответы

Ответ 1

Здесь реализуется алгоритм евклидова алгоритма, который возвращает наибольший общий делитель без выполнения распределения кучи.

Вы можете заменить ulong на uint, если это необходимо. Используется неподписанный тип, поскольку метод не работает для подписанных значений. Если вы знаете, что ваши значения a и b не являются отрицательными, вы можете вместо этого использовать long или int.

private static ulong GCD(ulong a, ulong b)
{
    while (a != 0 && b != 0)
    {
        if (a > b)
            a %= b;
        else
            b %= a;
    }

    return a == 0 ? b : a;
}

Этот метод используется в моей библиотеке metadata-extractor, где он связан с unit tests.

Ответ 2

Используя метод LINQ Aggregate:

static int GCD(int[] numbers)
{
    return numbers.Aggregate(GCD);
}

static int GCD(int a, int b)
{
    return b == 0 ? a : GCD(b, a % b);
}

Примечание: ответ выше заимствован из принятого ответа на Величайший общий делитель из набора из более чем 2 целых чисел.

Ответ 3

Вы можете попробовать this:

static int GreatestCommonDivisor(int[] numbers)
{
    return numbers.Aggregate(GCD);
}

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

Ответ 4

Попробуйте следующее:

public static int GCD(int p, int q)
{
    if(q == 0)
    {
         return p;
    }

    int r = p % q;

    return GCD(q, r);
}

Ответ 5

By using this, you can pass multiple values as well in the form of array:-


// pass all the values in array and call findGCD function
    int findGCD(int arr[], int n) 
    { 
        int gcd = arr[0]; 
        for (int i = 1; i < n; i++) {
            gcd = getGcd(arr[i], gcd); 
}

        return gcd; 
    } 

// check for gcd
int getGcd(int x, int y) 
    { 
        if (x == 0) 
            return y; 
        return gcd(y % x, x); 
    }

Ответ 6

    int a=789456;


    int b=97845645;
    if(a>b)     
    {

    }
    else
    {
        int temp=0;
        temp=a;
        a=b;
        b=temp;
    }
    int x=1;
    int y=0 ;

    for (int i =1 ; i < (b/2)+1 ; i++ )
    {

        if(a%i==0)
        {
             x=i;
        }
        if(b%i==0)
        {
             y=i;
        }
        if ((x==y)& x==i & y==i & i < a)
        {
            Console.WriteLine(i);
        }

    }