35

“两个整数的最大公约数是平均除以两个数字中的每一个的最大整数。编写返回两个整数的最大公约数的方法 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;
        }

  }
}
4

12 回答 12

83

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

如果需要，您可以替换ulong。uint使用无符号类型，因为该技术不适用于有符号值。如果你知道你的aandb值不是负数，你可以使用longorint代替。

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

    return a | b;
}

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

于 2017-01-20T14:38:46.780 回答
25

使用 LINQ 的聚合方法：

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 个整数中对最大公约数的公认答案借来的。

于 2013-08-30T21:44:03.390 回答
10

你可以尝试使用这个：

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

static int GreatestCommonDivisor(int x, int y)
{
return y == 0 ? x : GreatestCommonDivisor(y, x % y);
}
于 2013-08-30T21:41:09.580 回答
6

尝试这个：

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

    int r = p % q;

    return GCD(q, r);
}
于 2013-08-30T21:50:13.820 回答
2 
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); 
    } 
}
于 2019-10-27T10:54:37.360 回答
1 
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); 
    }
于 2018-12-08T10:42:51.517 回答
0

如果效率不是一个大问题，这将完成这项工作。

// gets greatest common divisor of A and B. 
var GCD=Enumerable.Range(1,Math.Min(A,B)).Last(n=>(A%n | B%n)==0);
于 2020-07-24T15:26:53.590 回答
0 
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();
于 2020-02-29T12:30:26.153 回答
0 
int[] nums = new int[] {6,12,24,48};
int GCD(int a, int b) => b == 0 ? a : GCD(b, a % b);
int FindGCD(int[] numbers) => numbers.Aggregate(GCD);

Console.WriteLine($"List of numbers ({String.Join(',',nums)})");
Console.WriteLine($"Smallest number: {nums.Min()}");
Console.WriteLine($"Largest number: {nums.Max()}");
Console.WriteLine($"Greatest common devisor of {nums.Min()} and {nums.Max()}: {GCD(nums.Min(),nums.Max())}");
Console.WriteLine($"Aggregate common devisor of array ({String.Join(',',nums)}): {FindGCD(nums)}");

数字列表 (6,12,24,48)

最小数量：6

最大数：48

6 和 48 的最大公约数：6

数组 (6,12,24,48) 的聚合公约数：6

于 2021-11-12T00:58:32.720 回答
0

这是一个简单的解决方案。您可以使用BigInteger获得最大公约数。只是不要忘记添加using System.Numerics;到代码的顶部。

using System.Numerics;

public class Program{
    public static void Main(String[] args){
        int n1 = 1;
        int n2 = 2;

        BigInteger gcd = BigInteger.GreatestCommonDivisor(n1,n2);
        Console.WriteLine(gcd);
    }
}

官方文档

于 2022-03-01T17:09:08.617 回答
-2 
using System;

//Write a function that returns the greatest common divisor (GCD) of two integers

namespace GCD_of_Two_Numbers
{
    class Program
    {
        public static void Gcd(int num1, int num2)
        {
            int[] temp1 = new int[num1];
            int[] temp2 = new int[num2];
            int[] common = new int[10];

            for(int i=2;i<num1/2;i++)
            {
                if(num1 % i ==0)
                {
                    temp1[i] = i;
                }
            }

            for (int i = 2; i < num2/2; i++)
            {
                if (num2 % i == 0)
                {
                    temp2[i] = i;
                }
            }
            int len = temp1.Length + temp2.Length;
            for(int i=0;i<len;i++)
            {
                if(temp1[i]==temp2[i])
                {
                    common[i] = temp1[i];
                }
            }

            int max_number = common[0];
            for(int i=0;i<common.Length;i++)
            {
                if(max_number < common[i])
                {
                    max_number = common[i];
                }
            }

            Console.WriteLine($"The Greatest Common Diviser is {max_number}");
        }
        
        static void Main(string[] args)
        {
            Gcd(32, 8);
        }
    }
}
于 2021-05-26T16:18:19.263 回答
-3 
    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);
        }

    }
于 2017-12-24T11:26:42.813 回答