C# 求最大公约数

C# find the greatest common divisor

提问by user2723261

"The greatest common divisor of two integers is the largest integer that evenly divides each of the two numbers. Write method Gcd that returns the greatest common divisor of two integers. Incorporate the method into an app that reads two values from the user and displays the result."

“两个整数的最大公约数是将两个数字中的每一个均等的最大整数。编写方法 Gcd，返回两个整数的最大公约数。将该方法合并到一个应用程序中，该应用程序从用户那里读取两个值并显示结果。”

(this is not homework, just an exercise in the book I'm using)

（这不是作业，只是我正在使用的书中的一个练习）

can you help me solve this? Here's what I've got so far.

你能帮我解决这个问题吗？这是我到目前为止所得到的。

(edit - I can submit the two numbers but it won't calculate the Gcd for me)

（编辑 - 我可以提交这两个数字，但它不会为我计算 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;
        }

  }
}

回答by Rahul Tripathi

You can try using this:

你可以尝试使用这个：

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

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

回答by Karl Anderson

Using LINQ's Aggregate method:

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

Note: answer above borrowed from accepted answer to Greatest Common Divisor from a set of more than 2 integers.

注意：上面的答案借用了对Greatest Common Divisor 的已接受答案from a set of more than 2 integers。

回答by user2623931

Try this:

尝试这个：

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

    int r = p % q;

    return GCD(q, r);
}

回答by Drew Noakes

Here's an implementation of the Euclidean algorithmthat returns the greatest common divisor without performing any heap allocation.

这是欧几里得算法的一个实现，它返回最大公约数而不执行任何堆分配。

You can substitute ulongfor uintif needed. An unsigned type is used, as the technique does not work for signed values. If you know your aand bvalues are not negative, you can use longor intinstead.

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

This method is used in my metadata-extractorlibrary, where it has associated unit tests.

这个方法用在我的元数据提取器库中，它有关联的单元测试。

回答by seyed

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

    }

回答by Chang

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

回答by Adil Rao

public class GCD 
{        
    public int generalizedGCD(int num, int[] arr)
    {
         int gcd = arr[0]; 

        for (int i = 1; i < num; i++) {
            gcd = getGcd(arr[i], gcd); 
        }

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

回答by Hulk Hogan

List<int> gcd = new List<int>();
int n1, n2;

bool com = false;

Console.WriteLine("Enter first number: ");
n1 = int.Parse(Console.ReadLine());
Console.WriteLine("Enter second number: ");
n2 = int.Parse(Console.ReadLine());

for(int i = 1; i <= n1; i++)
{
    if(n1 % i == 0 && n2% i == 0)
    {
        gcd.Add(i);
    }

    if(i == n1)
    {
        com = true;
    }
}

if(com == true)
{
    Console.WriteLine("GCD of {0} and {1} is {2}.", n1, n2, gcd[gcd.Count - 1]);
}
Console.ReadLine();