求最小公倍数

作者：追风剑情发布于：2016-5-5 10:30 分类：Algorithms

最小公倍数和最大公约数存在以下关系：

最大公因数×最小公倍数=两数的乘积

using System;
using System.Collections.Generic;
using System.Text;

namespace GCDTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("GcdLcm()");
            Console.WriteLine("{0}和{1}的最小公倍数={2}", 28, 14, GcdLcm(28, 14));
            Console.WriteLine("{0}和{1}的最小公倍数={2}", 58, 14, GcdLcm(58, 14));
            Console.WriteLine("{0}和{1}的最小公倍数={2}", 99, 21, GcdLcm(99, 21));

            Console.WriteLine("NormalLcm()");
            Console.WriteLine("{0}和{1}的最小公倍数={2}", 28, 14, NormalLcm(28, 14));
            Console.WriteLine("{0}和{1}的最小公倍数={2}", 58, 14, NormalLcm(58, 14));
            Console.WriteLine("{0}和{1}的最小公倍数={2}", 99, 21, NormalLcm(99, 21));

            Console.Read();
        }

        /// <summary>
        /// 辗转相除法求a和b的最大公约数
        /// </summary>
        public static int EuclidGcd(int a, int b)
        {
            if (b > a)
            {
                int tmp = a;
                a = b;
                b = tmp;
            }

            while (b != 0)
            {
                int tmp_b = b;
                b = a % b;
                a = tmp_b;
            }

            return a;
        }

        /// <summary>
        /// 求a和b的最小公倍数
        /// 缺点: 如果a、b过大，会导致乘积溢出。
        /// </summary>
        public static int GcdLcm(int a, int b)
        {
            int r = (a * b) / EuclidGcd(a, b);
            return r;
        }

        /// <summary>
        /// 求a和b的最小公倍数
        /// 缺点: 如果a非常小，b非常大，会导致while循环相当漫长。
        /// </summary>
        public static int NormalLcm(int a, int b)
        {
            int r = a;
            while (r % b != 0)
            {
                r += a;
            }
            return r;
        }
    }
}

运行结果