ACM: Q001 (★☆☆☆☆)

請寫一個程式求出2個數的GCD(最大公因數)

.

Input and Output

輸入包含好幾筆資料，每筆資料一行，包含2個整數a,b。(0<a,b<10000000) 0 0代表輸入結束。 對每行輸入，輸出這2個數的GCD

.

Sample Input 12 36 25 24 0 0

Sample Output GCD(12,36)=12 GCD(25,24)=1

解法：

此題為最大公因數的求法，運用輾轉相除法的原理來做

Ex1: 12 " 36 36 --------- 12 0

Ex2: x y 50 " 17 --- 50 mod 17 = 16 34 --------- 16 " 17 --- 17 mod 16 = 1 16 --------- 16 " 1 --- 16 mod 1 = 0 16 --------- '此時 x mod y = 0，y為最大公因數 0

.

.

程式碼:(VB6)

Private Sub Form_Load()
    ifile = App.Path & "test.txt"
    ofile = App.Path & "result.txt"
Open ifile For Input As #1
Open ofile For Output As #2
    Do Until EOF(1)
    Input #1, x
    Input #1, y
        a = x
        b = y
        If x = 0 And y = 0 Then
            End
        End If
        While x Mod y <> 0
            z = x Mod y
            x = y
            y = z
        End While
    Print #2, "GCD(" & a & "," & b & ")=" & Trim(y)
    Loop
    Close()
    End
End Sub