a007. 判斷質數

contents

1. 1. 題目
   1. 1.1. 內容：
   2. 1.2. 輸入說明：
   3. 1.3. 輸出說明：
   4. 1.4. 範例輸入：
   5. 1.5. 範例輸出：
2. 2. 解法

題目

內容：

請判斷某數是否為質數

輸入說明：

輸入有多組測試資料（以EOF結尾），每組測試資料占一行，只包含一個整數x, 2 ≦ x ≦ 2147483647。

輸出說明：

對於每組測試資料，如果輸入的x為質數，則輸出一行「質數」（不含引號）；否則輸出一行「非質數」（不含引號）。詳見範例測試資料。

範例輸入：

13
14

範例輸出：

質數
非質數

---

解法

• 作法：
  Miller-Rabin Algorithm

a007.cpp

/**********************************************************************************/
/*  Problem: a007 "判斷質數"                                                  */
/*  Language: CPP (715 Bytes)                                                     */
/*  Result: AC(0.2s, 224KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:25:42                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
    long long Ans = 1, t = x;
    while(n) {
        if(n&1)
            Ans *= t, Ans %= mod;
        t *= t, t %= mod, n >>= 1;
    }
    return (int)Ans;
}
int JudgePrime(int n) {
    if(n == 2 || n == 3)    return 1;
    if(n == 1)    return 0;
    if(!(n&1))    return 0;
    int a, x, flag = 1, t;
    for(a = 0; a < 2; a++) {
        x = rand()%(n-4)+2;
        t = Pow(x, n-1, n);
        if(t != 1)    return 0;
    }
    return 1;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        if(JudgePrime(n))    puts("質數");
        else    puts("非質數");
    }
    return 0;
}