using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        public int k = 1;
        static void Main(string[] args)
        {
            Console.WriteLine("Give the natural number a:");
            int a = int.Parse(Console.ReadLine());
            Console.WriteLine("Give the natural number b:");
            int b = int.Parse(Console.ReadLine());
            Console.WriteLine();
            Console.Write("gcd({0},{1})=", a, b);
            Console.WriteLine("The greatest common divisor of {0} and {1} is {2}", a, b, gcd(a, b));
            Console.WriteLine();
            Console.Write("gcd({0},{1})=", a, b);
            Console.WriteLine("The greatest common divisor of {0} and {1} is {2} (with Euclidean algorithm)", a, b, gcd2(a, b));
            Console.WriteLine();
            Console.Write("gcd({0},{1})=", a, b);
            Console.WriteLine("The greatest common divisor of {0} and {1} is {2} (with binary gcd algorithm)", a, b, gcd3(a, b));
            Console.ReadLine();
        }

        static public int gcd(int a,int b) 
        {
            int s;
            if (a < b)
            {
                Console.Write("gcd({0},{1})=", b, a);
                s = gcd(b, a);
            }
            else 
            {
                if (b == 0)
                {
                    Console.WriteLine("{0}", a);
                    s = a;
                }
                else
                {
                    Console.Write("gcd({0},{1})=", a-b, b);
                    s = gcd(a - b, b);
                }
            }
            return s;
        }

        static public int gcd2(int a, int b)
        {
            int s;
            if (b == 0)
            {
                Console.WriteLine("{0}", a);
                s = a;
            }
            else
            {
                Console.Write("gcd({0},{1})=", b, a % b);
                s = gcd2(b, a % b);
            }
            return s;
        }

        static public int gcd3(int a, int b)
        {
            int s;
            if (a < b)
            {
                Console.Write("gcd({0},{1})=", b, a);
                s = gcd3(b, a);
            }
            else
            if (b == 0)
            {
                Console.WriteLine("{0}", a);
                s = a;
            }
            else
                if (a % 2 == 0 & b % 2 == 0)
            {
                Console.Write("2*gcd({0},{1})=", a / 2, b / 2);
                s = 2 * gcd3(a / 2, b / 2);
            }
            else
            if (a % 2 == 0 & b % 2 != 0)
            {
                Console.Write("gcd({0},{1})=", a / 2, b);
                s = gcd3(a / 2, b);
            }
            else
            if (a % 2 != 0 & b % 2 == 0)
            {
                Console.Write("gcd({0},{1})=", a, b / 2);
                s = gcd3(a, b / 2);
            }
            else
            {
                Console.Write("gcd({0},{1})=", b, (a - b) / 2);
                s = gcd3(b, (a - b) / 2);
            }
            return s;
        }
    }
}