2015年7月24日 星期五

C++進階研習：a007判斷質數

           No comments   
7/23 + 7/30  解 zerojudge.tw 中之 a007 判斷質數

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 46340
using namespace std;

bool c[maxn+10];
vector <int> p;

// 以下 isp 為函式， 傳入 n 判斷是否為質數 
bool isp(int n)
{
  if(n<=maxn) return( !c[n] );
  int q = (int) sqrt(n);
  int k;
  for(k=0; k<p.size() && p[k]<=q ; ++k)
    if(n%p[k]==0) return false;
  return true;     
}

int main( )  // 主程式開始
{
  int i,j,k;
  memset(c,0,sizeof(c));    // 將 c 陣列全清為 0
  c[0]=c[1]=1;
  for(i=2;i<=maxn;++i)
  {
     if(c[i]==1) continue;   //非質數
     p.push_back(i);         // i是質數，放入 p 中 
     // 以下將是質數 i 的倍數 註記為非質數
     for(j=i+i; j<=maxn; j+=i)
       c[j]=1;                   
  }
  int n;
  while( cin >> n )   // 讀資料直到 EOF
  {
    if( isp(n) ) cout << "質數" << endl;
    else cout << "非質數" << endl; 
  }
  return 0;
}

2015年7月17日 星期五

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

           No comments   
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

2015年7月2日 星期四