C# find the greatest common divisor

Question

"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."

(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)

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

  }
}

I can submit the two numbers but it won't calculate the Gcd for me — user2723261, Aug 30 '13 at 21:41
You should check out the [Euclidean algorithm](http://en.wikipedia.org/wiki/Euclidean_algorithm). — Daniel Fischer, Aug 30 '13 at 21:41
`for (int i = m; i <= 1; i--)` won't execute when `m > 1`, you meant `i >= 1`. — Daniel Fischer, Aug 30 '13 at 21:42

Drew Noakes · Answer 1 · 2020-07-24T23:33:11.247

98

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

You can substitute ulong for uint if needed. An unsigned type is used, as the technique does not work for signed values. If you know your a and b values are not negative, you can use long or int instead.

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

    return a | b;
}

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

edited Jul 24 '20 at 23:33

answered Jan 20 '17 at 14:38

Drew Noakes

300,895
165
679
742

9

This is the best answer on the page; it does not do any expensive and extraneous recursive calls, and actually answers the OP's specific question (unlike a few other answers which for some reason digress on GCD of a set). – Glenn Slayden Jun 25 '17 at 22:42
5

They compute the GCD of a set because they're copying and pasting code they don't understand from an answer to a separate question. – Daniel McLaury Aug 18 '17 at 03:04
5

Nice and clean - no LINQ-soup mixed in. And with that, exactly what I was looking for my own little "dilemma". :D – Scre Aug 26 '17 at 20:16
4

Oh, this does work just fine with negative input(s): just flip the sign of negative values before entering the while-loop... if(a<0)a=-a; if(b<0)b=-b; – Scre Aug 27 '17 at 10:08
1

Last line can be writen: "return a | b;" . As one of them will always be zero, performing an OR operation with both will result the non-zero value. – Zuabros Jul 24 '20 at 23:21
Good idea. It avoids a branch. – Drew Noakes Jul 24 '20 at 23:32

score 28 · Answer 2 · edited Jan 17 '19 at 20:33

28

Using LINQ's Aggregate method:

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.

edited Jan 17 '19 at 20:33

Jim Buck

2,383
23
42

answered Aug 30 '13 at 21:44

Karl Anderson

34,606
12
65
80

9

This is incorrect. You can't split this answer into LINQ and non-LINQ, the solution is the 2 methods working together. The first method is calling the second method in the Aggregate call, this is a bit confusing because the names are the same. – Metro101 Dec 10 '14 at 21:46
4

it would be very nice to reply to this, Karl. Your answer is indeed incorrect. – Don Larynx Dec 30 '14 at 23:35
@DonLarynx Is this answer still incorrect after the most recent edit? Seems like at least the second function works to me, but I could definitely be wrong. – PerpetualStudent Jul 22 '20 at 19:26

score 11 · Answer 3 · edited Dec 25 '19 at 07:47

11

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

edited Dec 25 '19 at 07:47

Arsen Khachaturyan

7,904
4
42
42

answered Aug 30 '13 at 21:41

Rahul Tripathi

168,305
31
280
331

return x*y == 0 ? x : GreatestCommonDivisor(y, x % y); this version has more accurate – Çağlar Can Sarıkaya Nov 28 '21 at 20:06

score 6 · Answer 4 · answered Aug 30 '13 at 21:50

6

Try this:

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

    int r = p % q;

    return GCD(q, r);
}

answered Aug 30 '13 at 21:50

user2623931

61
2

score 4 · Answer 5 · edited Mar 01 '22 at 20:51

Here is a simple solution. You can use BigInteger to get the greatest common divisor. Just do not forget to add using System.Numerics; to the top of your code.

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

score 2 · Answer 6 · answered Oct 27 '19 at 10:54

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

score 1 · Answer 7 · answered Dec 08 '18 at 10:42

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

Zuabros · Answer 8 · 2020-07-24T22:51:15.060

1

If efficiency is not a big concern this will do the job.

// gets greatest common divisor of A and B. 
var GCD=Enumerable.Range(1,Math.Min(A,B)).Last(n=>(A%n | B%n)==0);

edited Jul 24 '20 at 22:51

answered Jul 24 '20 at 15:26

Zuabros

252
1
5

score 0 · Answer 9 · edited Feb 29 '20 at 13:12

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

score 0 · Answer 10 · answered Nov 12 '21 at 00:58

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

List of numbers (6,12,24,48)

Smallest number: 6

Largest number: 48

Greatest common devisor of 6 and 48: 6

Aggregate common devisor of array (6,12,24,48): 6

score 0 · Answer 11 · edited Apr 19 '23 at 16:17

    public class Program
{
    public static int GETGCD(int[] a)
    {
        int index = 0;
        int answer = 0;
        while (index < a.Length)
        {
            for (int x = 0; x < a.Length; x++)
            {
                if (a[x] % a[index] == 0)
                {
                    answer = a[index];
                }
                else
                {
                    answer = 0;
                    x += a.Length;
                }
            }
            if (answer == 0)
            {
                index++;
            }
            if (answer != 0)
            {
                index += a.Length;
            }

        }
        if (answer == 0)
        {
            answer = 1;
        }
        return answer;
    }

    public static void Main(string[] args)
    {
        int[] a = { 2, 3, 7, 8, 9, 10 };
        int[] b = { 2, 4, 6, 8, 10 };

        Console.WriteLine("Greatest Common Divisor of {" + String.Join(",", a.Select(i => i.ToString()).ToArray()) + "} is " + GETGCD(a));
        Console.WriteLine("Greatest Common Divisor of {" + String.Join(",", b.Select(i => i.ToString()).ToArray()) + "} is " + GETGCD(b));
    }
}

This is fully running code. Just copy and paste it. Screenshot of the output is attached.

score -2 · Answer 12 · edited May 27 '21 at 05:16

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

score -3 · Answer 13 · answered Dec 24 '17 at 11:26

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

    }

C# find the greatest common divisor

13 Answers13

Linked