Monday, April 30, 2012

Exercise: Finding Greatest Common Divisor (Euclidean Algorithm)

Finding the GCD for 2 numbers

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;


namespace CS
{
public static class Helpers
{
public static BigInteger GCD_Loop(BigInteger A, BigInteger B)
{
BigInteger R = BigInteger.One;
while (B != 0)
{
R = A % B;
A = B;
B = R;
}
return A;
}
public static BigInteger GCD_Euclidean(BigInteger A, BigInteger B)
{
if (B == 0)
return A;
if (A == 0)
return B;
if(A>B)
return GCD_Euclidean(B, A % B);
else
return GCD_Euclidean(B % A, A);
}
}
}