先計算出範圍內可能的質因數,再利用其計算,否則時間會不足。
Calculate all the primes in the range first, otherwise the time will be exceeded.

ZeroJudge Link (Zh)

#include <stdio.h>
#include <math.h>
#include <limits.h>

main() {
  int primes[5000];
  int top = 0;
  int maxPrime = sqrt(INT_MAX) + 1;
  int input, num, i;

  for(num = 2; num <= maxPrime; num++) {
    int maxSearch = sqrt(num) + 1;
    int isPrime = 1;
    for(i = 0; i < top && primes[i] < maxSearch; i++) {
      if(num % primes[i] == 0) {
        isPrime = 0;
        break;
      }
    }
    if(isPrime) primes[top++] = num;
  }

  while(scanf("%d", &input) != EOF) {
    if(input < 2) input = 4;
    int maxSearch = sqrt(input) + 1;
    int isPrime = 1;
    for(i = 0; i < top && primes[i] < maxSearch; i++) {
      if(input % primes[i] == 0) {
        isPrime = 0;
        break;
      }
    }
    printf("%s\n", isPrime ? "質數" : "非質數");
  }

  return 0;
}