歐幾里德算法:
Code
using System;using System.Collections.Generic;using System.Text;namespace ojilide
{
class Program
{ static void Main(string[] args) { Console.Write("最大公約數為{0}",gcd(10,5)); Console.WriteLine(); Console.Write("最小公倍數為{0}", gbs(2, 3)); Console.WriteLine();
} //歐幾里德算法又稱輾轉相除法，用于計算兩個整數a,b的最大公約數。 //其計算原理依賴于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) //其算法用C#語言描述為 /**//// <summary> /// 最大公約數 /// </summary> /// <param name="a"></param> /// <param name="b"></param> /// <returns></returns> public static int gcd(int a, int b) { if (a == 0) { return b; } if (b == 0) { return a; } if (a < b) { int temp; temp = b; b = a; a = temp; } while (b != 0) { int temp; temp = a % b; a = b; b = temp; } return a; } /**//// <summary> /// 附：最小公倍數 /// </summary> /// <param name="m"></param> /// <param name="n"></param> /// <returns></returns> public static int gbs(int m, int n) { return m * n / gcd(m, n); } }
}
浙公網安備 33010602011771號