C#找到最大的公约数

Question

"两个整数的最大公约数是最大的整数,它将两个数字中的每一个均分.写入方法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;
        }

  }
}

Answer 1

这是Euclidean算法的一个实现,它返回最大公约数而不执行任何堆分配.

您也可以替换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;
}

此方法用于我的元数据提取器库,它具有关联的单元测试.

Answer 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个整数的最大公约数的公认答案.

Answer 3

尝试这个：

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

    int r = p % q;

    return GCD(q, r);
}

Answer 4

你可以试试这个: -

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

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