目录
1.最大公约数
最大公约数（Greatest Common Divisor，GCD）是两个或多个整数共有的最大的能被无余地整除的数。例如，12 和 18 的最大公约数是 6。最大公约数可以通过辗转相除法、欧几里得算法（或更相减损术等方法）求解。
2.欧几里得算法
欧几里得算法（Euclidean Algorithm）是一种用于计算两个整数的最大公约数的高效算法，基于以下原理：如果 n1 和 n2 是两个整数，且 n1 > n2，那么 n1 和 n2 的最大公约数等于 n2 和 n1%n2 的最大公约数。这个算法会不断将较大的数替换为较小的数，并将较小的数替换为两者的余数，直到较小的数为 0，此时较大的数就是两个数的最大公约数。
// 欧几里得算法（Euclidean Algorithm）实现求最大公约数
namespace _138
{
class Program
{
public static float GreatestComDivisor(int n1, int n2)
{
int temp = Math.Max(n1, n2);//求两个数的最大值
n2 = Math.Min(n1, n2); //求两个数中的最小值
n1 = temp; //记录临时值
while (n2 != 0)
{
n1 = n1 > n2 ? n1 : n2; //使n1中的数大于n2中的数
int m = n1 % n2; //记录n1求余n2的结果
n1 = n2; //交换两个数
n2 = m; //记录求余结果
}
return n1;
}
static void Main(string[] args)
{
ArgumentNullException.ThrowIfNull(args);
while (true)
{
Console.Write("请输入第一个数：");
int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数
Console.Write("请输入第二个数：");
int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数
if (n1 * n2 != 0) //判断两个数中的一个是否为0
{
Console.WriteLine("最大公约数:" + GreatestComDivisor(n1, n2));
}
else
{
Console.WriteLine("这两个数不能为0。");
}
}
}
}
}
//运行结果：
/*
请输入第一个数：12
请输入第二个数：18
最大公约数:6
请输入第一个数：34
请输入第二个数：17
最大公约数:17
请输入第一个数：
*/3.辗转相除法
辗转相除法（也称为更相减损术）。辗转相除法是一种用于计算两个整数的最大公约数的算法，基于以下原理：如果 a 和 b 是两个整数，且 a > b，那么 a 和 b 的最大公约数等于 b 和 a % b 的最大公约数。这个算法会不断将较大的数替换为较小的数，并将较小的数替换为两者的余数，直到较小的数为 0，此时较大的数就是两个数的最大公约数。
// 用辗转相除法计算两个整数的最大公约数
namespace _138_1
{
class Program
{
public static int GreatestComDivisor(int a, int b)
{
while (b != 0)
{
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
static void Main(string[] args)
{
ArgumentNullException.ThrowIfNull(args);
while (true)
{
Console.Write("请输入第一个数：");
int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数
Console.Write("请输入第二个数：");
int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数
if (n1 * n2 != 0) //判断两个数中的一个是否为0
{
Console.WriteLine("最大公约数:" + GreatestComDivisor(n1, n2));
}
else
{
Console.WriteLine("这两个数不能为0。");
}
}
}
}
}
//运行结果：
/*
请输入第一个数：12
请输入第二个数：18
最大公约数:6
请输入第一个数：34
请输入第二个数：17
最大公约数:17
请输入第一个数：
*/
