[C#][VB.NET]最大公因數 & 最小公倍數

翻閱程式發現以前在處理合併儲存格時,為該功能撰寫了最大公因數與最小公倍數的處理,這邊稍微整理記錄一下。

最大公因數的取法為使用遞迴去實作輾轉相除法,最小公倍數則是利用最大公因數與下面公式來計算:

image

image

程式碼

C#

        private int GCD(int num1, int num2)
{
int min = 0;
int max = 0;
int maxModMin = 0;
min = Math.Min(num1, num2);
max = Math.Max(num1, num2);
maxModMin = max % min;
return maxModMin > 0 ? GCD(min, maxModMin) : min;
}

private int LCM(int num1, int num2)
{
return num1 * num2 / GCD(num1, num2);
}


VB.NET

    Private Function GCD(ByVal num1 As Integer, ByVal num2 As Integer) As Integer
Dim min, max, maxModMin As Integer
min = Math.Min(num1, num2)
max = Math.Max(num1, num2)
maxModMin = max Mod min
Return If(maxModMin > 0, gcd(min, maxModMin), min)
End Function

Private Function LCM(ByVal num1 As Integer, ByVal num2 As Integer) As Integer
Return num1 * num2 / GCD(num1, num2)
End Function

完整範例

C#

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

namespace ConsoleApplication1
{
class Program
{
private static int GCD(int num1, int num2)
{
int min = 0;
int max = 0;
int maxModMin = 0;
min = Math.Min(num1, num2);
max = Math.Max(num1, num2);
maxModMin = max % min;
return maxModMin > 0 ? GCD(min, maxModMin) : min;
}

private static int LCM(int num1, int num2)
{
return num1 * num2 / GCD(num1, num2);
}

static void Main(string[] args)
{
const int EXAMPLE_COUNT = 5;
const int MIN_RANDOM_VALUE = 2;
const int MAX_RANDOM_VALUE = 50;

int num1, num2;
Random ran = new Random();

Console.WriteLine(“GCD…”);
for (int i = 0; i < EXAMPLE_COUNT; ++i)
{
num1 = ran.Next(MIN_RANDOM_VALUE,MAX_RANDOM_VALUE);
num2 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE);
Console.WriteLine(“GCD({0},{1}) = {2}”, num1, num2, GCD(num1, num2).ToString());
}

Console.WriteLine();
Console.WriteLine(“LCM…”);
for (int i = 0; i < EXAMPLE_COUNT; ++i)
{
num1 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE);
num2 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE);
Console.WriteLine(“LCM({0},{1}) = {2}”, num1, num2, LCM(num1, num2).ToString());
}
}
}
}

VB.NET

Module Module1


Private Function GCD(ByVal num1 As Integer, ByVal num2 As Integer) As Integer
Dim min, max, maxModMin As Integer
min = Math.Min(num1, num2)
max = Math.Max(num1, num2)
maxModMin = max Mod min
Return If(maxModMin > 0, gcd(min, maxModMin), min)
End Function

Private Function LCM(ByVal num1 As Integer, ByVal num2 As Integer) As Integer
Return num1 * num2 / GCD(num1, num2)
End Function

Sub Main()
Const EXAMPLE_COUNT As Integer = 5
Const MIN_RANDOM_VALUE As Integer = 2
Const MAX_RANDOM_VALUE As Integer = 50

Dim num1 As Integer, num2 As Integer
Dim ran As New Random()

Console.WriteLine(“GCD…”)
For i As Integer = 0 To EXAMPLE_COUNT - 1
num1 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE)
num2 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE)
Console.WriteLine(“GCD({0},{1}) = {2}”, num1, num2, GCD(num1, num2).ToString())
Next

Console.WriteLine()
Console.WriteLine(“LCM…”)
For i As Integer = 0 To EXAMPLE_COUNT - 1
num1 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE)
num2 = ran.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE)
Console.WriteLine(“LCM({0},{1}) = {2}”, num1, num2, LCM(num1, num2).ToString())
Next
End Sub

End Module

運行結果如下:

image