102年模擬題 (第3題-數學問題：子題1-質因數乘積與最大公因數)

Rem  102年模擬題 Problem3:數學問題 子題1：質因數乘積及最大公因數

 Dim p(100) As Integer   ' 2 ~ 255=SQRT(65535) 之間的質數，p(0)=2,(1)=3,(2)=5,(3)=7 ....,p(53)=251
 Dim pcnt As Integer = 1   '質數表個數
 Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    '建質數表
    p(0) = 2  '第1個質數 2
    For k = 3 To 255 Step 2
        If isp(k) Then
            p(pcnt) = k
            pcnt += 1
        End If
    Next
    ' Debug.Print(pcnt & "," & p(pcnt - 1)) 2~255之間共有54個質數、最大為251
    Dim line = Split(TextBox1.Text, vbNewLine)  '分行
    Dim n As Integer = line(0)  ' 共有幾筆
    For i = 1 To n  '每一行處理一次，印一個 質因數乘積、最大公因數
        Dim dat() = Split(line(i), ",")
        out.Text &= fun1(Val(dat(0))) & " ," & fun2(Val(dat(0)), Val(dat(1))) & vbCrLf
    Next
 End Sub

 Function isp(ByVal k As Integer) As Boolean   '判斷 k 是否為質數
   isp = True
   If k < 2 Then Return False               ' 1非質數
   Dim q As Integer = Int(Math.Sqrt(k))     ' q為 <= k的平方根
   For i = 0 To pcnt - 1
       If k = p(i) Or q < p(i) Then Return True
       If k Mod p(i) = 0 Then Return False
   Next
 End Function

'函式1： 傳入 k 傳回 K的質因數乘積 例如 K=288傳回 2^5*3^2， K=12傳回 2^2*3
 Function fun1(ByVal k As Integer) As String
   '若 k 是質數，直接傳回
   If isp(k) Then Return "" & k
   fun1 = ""   '傳入 k 傳回 K的質因數乘積 例如 K=288傳回 2^5*3^2， K=12傳回 2^2*3
   Dim f(100) As Integer  '初始值為 f(i)=0  
   '  f(0)為p(0)質數2的次方， f(1)為3的次方數, f(2)為5的次方數
   Dim i = 0
   While (k <> 1 And i < pcnt)
       If k Mod p(i) = 0 Then ' k被某質數整除，該質數的次方+1
           k /= p(i)
           f(i) += 1
       Else                   '不整除
           i += 1             '試下一個質數
       End If
   End While
   Dim first As Boolean = True
   For j = 0 To i
       If f(j) > 0 Then
           If first Then first = False Else fun1 &= "*"
           fun1 &= p(j)
           If f(j) > 1 Then fun1 &= "^" & f(j)
       End If
   Next
   If k > 1 Then fun1 &= "*" & k '因為質數表 p(53)最大只存251，若除完後 k>251 的則直接印出
 End Function

'函式2：傳入兩數 a,b 傳回最大公因數
 Function fun2(ByVal a As Integer, ByVal b As Integer) As Integer
   Dim c = a Mod b
   Do While c <> 0
       a = b
       b = c
       c = a Mod b
   Loop
   Return b
 End Function

輸入資料如下有4筆
4
32820,100
288,3888
12,18
17,1
--輸出Ans 如下
2^2*3*5*547, 20
2^5*3^2, 144
2^2*3, 6
17, 1