CSHARP

Program to find GCD or HCF of two numbers c#

// C# program to find GCD of two numbers
using System;
class GFG
{
    static int [,]dp = new int[1001, 1001];
   
    // Recursive function to return gcd of a and b
    static int gcd(int a, int b)
    {
       
        // Everything divides 0
        if (a == 0)
          return b;
        if (b == 0)
          return a;
      
        // base case
        if (a == b)
            return a;
      
    // if a value is already
    // present in dp
    if(dp[a, b] != -1)
        return dp[a, b];
 
    // a is greater
    if (a > b)
        dp[a, b] = gcd(a-b, b);
     
    // b is greater
    else
        dp[a, b] = gcd(a, b-a);
     
    // return dp
    return dp[a, b];
    }
     
    // Driver method
    public static void Main()
    {
        for(int i = 0; i < 1001; i++) {
            for(int j = 0; j < 1001; j++) {
                dp[i, j] = -1;
            }
        }
        int a = 98, b = 56;
        Console.Write("GCD of " + a +" and " + b + " is " + gcd(a, b));
    }
}
 
// This code is contributed by Samim Hossain Mondal.