logo标签列表

C#寻找最大公约数

c#math
38

两个整数的最大公约数是能够同时整除这两个数的最大的整数。编写一个方法 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;
        }

  }
}
我可以提交这两个数字，但它不会为我计算最大公约数。 - user2723261
1
你应该查看欧几里得算法。 - Daniel Fischer
2
当 m > 1 时，for (int i = m; i <= 1; i--) 不会执行，你的意思是 i >= 1。 - Daniel Fischer
13个回答
98

这是一个实现欧几里得算法的例子，它可以在不进行任何堆分配的情况下返回最大公约数。

如果需要，您可以将uint替换为ulong。使用无符号类型，因为该技术不适用于带符号的值。如果您知道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 | b;
}

这种方法在我的metadata-extractor库中使用，其中它有关联的单元测试。

9
这是该页面上最佳的答案；它没有做任何昂贵和不必要的递归调用，并且实际回答了 OP 的具体问题（与其他答案不同，它们因某种原因离题谈起集合的最大公约数）。 - Glenn Slayden
5
他们计算一个集合的最大公约数是因为他们复制并粘贴了一段自己不理解的代码，这段代码来自于另一个问题的答案。 - Daniel McLaury
5
干净利落 - 没有混杂着LINQ的代码。这正是我为自己的小“困境”所寻找的。 :D - Scre
4
这段话的意思是：哦，这个方法对负数也适用：在进入 while 循环之前，只需将负值取反即可... 如果 a<0，则令a=-a；如果 b<0，则令b=-b。 - Scre
1
最后一行可以写成："return a | b;"。因为其中一个值总是为零，对两个值进行或运算将得到非零值。 - Zuabros
好主意。它避免了分支。 - Drew Noakes
28

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

注意：上面的答案摘自一个包含两个以上整数的最大公约数的已接受答案。

9
这是不正确的。你不能将这个答案分为 LINQ 和非 LINQ 部分，解决方案是两种方法一起工作。第一个方法在 Aggregate 调用中调用第二个方法，这有点混乱，因为它们的名称相同。 - Metro101
4
卡尔，如果您能回复一下就非常好了。您的回答确实是不正确的。 - Don Larynx
@DonLarynx 最近的修改后，这个答案还是不正确吗？至少第二个函数看起来对我是有效的，但我可能错了。 - PerpetualStudent
11

你可以尝试使用这个：

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

static int GreatestCommonDivisor(int x, int y)
{
return y == 0 ? x : GreatestCommonDivisor(y, x % y);
}
返回 x*y == 0 ? x : GreatestCommonDivisor(y, x % y); 这个版本更准确。 - Çağlar Can Sarıkaya
6

试试这个：

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

    int r = p % q;

    return GCD(q, r);
}
4

这里有一个简单的解决方案。 您可以使用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);
    }
}

Offical Documentation

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); 
    } 
}
1
如果效率不是很重要的话，这个就可以胜任工作了。
// gets greatest common divisor of A and B. 
var GCD=Enumerable.Range(1,Math.Min(A,B)).Last(n=>(A%n | B%n)==0);
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); 
    }
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

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();
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接