先計算出範圍內可能的質因數，再利用其計算，否則時間會不足。
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;
}