1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| #include <stdio.h> #define N 1000005 int isPrime[N + 1];
int main() { int n; scanf("%d", &n); for (int i = 0; i <= N; i++) isPrime[i] = 1; isPrime[0] = isPrime[1] = 0; for (int i = 2; i <= N; i++) { for (int j = 2 * i; j <= N; j += i) isPrime[j] = 0; } while(n--) { int x; scanf("%d", &x); if (isPrime[x]) { printf("%d is prime\n", x); } else { printf("%d is not prime\n", x); } } return 0; }
|