a007: 判斷質數

2019-08-12

內容

請判斷某數是否為質數

輸入

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

測試資料至多有 200000 筆。

13
14

輸出

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

質數
非質數

解題思路

先建值數表，由於一個數不包含自己的因數最大值為該數的開根號，而本題最大值為 2147483647，所以值數表最大值大於 √2147483647 (46341) 即可。

接下來每筆輸入都先判斷是否在值數表的範圍內，在範圍內就用 bsearch()查表，範圍外就從值數表第 1 項開始試除到大於 √輸入值為止。

完整程式碼

AC (0.5s, 200KB)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 47000

int primeList[5000], pLen, n;
char isPrime;

int cmp(const void* lhs, const void* rhs)
{
    return (*(int*)lhs - *(int*)rhs);
}

void SetPrimeList()
{
    char isNot[MAX] = { 0 };
    primeList[pLen++] = 2;
    for (int i = 3; i < MAX; i += 2)
    {
        if (isNot[i])continue;
        primeList[pLen++] = i;
        for (int j = i << 1; j < MAX; j += i)
            isNot[j] = 1;
    }
}

int main()
{
    SetPrimeList();
    while (scanf(" %d", &n) == 1)
    {
        isPrime = 0;
        if (n < MAX)
        {
            int* item = (int*)bsearch(&n, primeList, pLen, sizeof(int), cmp);
            isPrime = (item != NULL);
        }
        else
        {
            isPrime = 1;
            for (int i = 0, max = sqrt(n); primeList[i] <= max; i++)
            {
                if (!(n % primeList[i]))
                {
                    isPrime = 0;
                    break;
                }
            }
        }
        puts(isPrime ? "質數" : "非質數");
    }
    return 0;
}