#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main() {
    char eratoTable[5793];
    int primeCount = 0;
    int primeList[46340] = {0};
    int i, j;
 
    for (i = 0; i < 5793; eratoTable[i++] = 0);
 
    for (i = 2; i < 5793; i++) {
        if ( (eratoTable[i / 8] >> (i % 8)) & 1) continue;
        for (j = i * 2; j < 46340; j += i) {
            eratoTable[j / 8] = eratoTable[j / 8] | (1 << (j % 8));
        }
    }
    for (i = 2; i < 46340; i++) {
        if ( !(eratoTable[i / 8] >> (i % 8) & 1) ) {
            primeList[primeCount++] = i;
        }
    }
    primeList[primeCount] = 0x7fffffff;
 
    int input, sqrtInput;
    while (scanf("%d", &input) != EOF) {
        sqrtInput = (int)sqrt(input);
        for (i = 0; primeList[i] <= sqrtInput; i++) {
            if (input % primeList[i] == 0) {
                printf("非");
                break;
            }
        }
        printf("質數\n");
    }
 
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1hdGguaD4KCmludCBtYWluKCkgewogICAgY2hhciBlcmF0b1RhYmxlWzU3OTNdOwogICAgaW50IHByaW1lQ291bnQgPSAwOwogICAgaW50IHByaW1lTGlzdFs0NjM0MF0gPSB7MH07CiAgICBpbnQgaSwgajsKCiAgICBmb3IgKGkgPSAwOyBpIDwgNTc5MzsgZXJhdG9UYWJsZVtpKytdID0gMCk7CgogICAgZm9yIChpID0gMjsgaSA8IDU3OTM7IGkrKykgewogICAgICAgIGlmICggKGVyYXRvVGFibGVbaSAvIDhdID4+IChpICUgOCkpICYgMSkgY29udGludWU7CiAgICAgICAgZm9yIChqID0gaSAqIDI7IGogPCA0NjM0MDsgaiArPSBpKSB7CiAgICAgICAgICAgIGVyYXRvVGFibGVbaiAvIDhdID0gZXJhdG9UYWJsZVtqIC8gOF0gfCAoMSA8PCAoaiAlIDgpKTsKICAgICAgICB9CiAgICB9CiAgICBmb3IgKGkgPSAyOyBpIDwgNDYzNDA7IGkrKykgewogICAgICAgIGlmICggIShlcmF0b1RhYmxlW2kgLyA4XSA+PiAoaSAlIDgpICYgMSkgKSB7CiAgICAgICAgICAgIHByaW1lTGlzdFtwcmltZUNvdW50KytdID0gaTsKICAgICAgICB9CiAgICB9CiAgICBwcmltZUxpc3RbcHJpbWVDb3VudF0gPSAweDdmZmZmZmZmOwoKICAgIGludCBpbnB1dCwgc3FydElucHV0OwogICAgd2hpbGUgKHNjYW5mKCIlZCIsICZpbnB1dCkgIT0gRU9GKSB7CiAgICAgICAgc3FydElucHV0ID0gKGludClzcXJ0KGlucHV0KTsKICAgICAgICBmb3IgKGkgPSAwOyBwcmltZUxpc3RbaV0gPD0gc3FydElucHV0OyBpKyspIHsKICAgICAgICAgICAgaWYgKGlucHV0ICUgcHJpbWVMaXN0W2ldID09IDApIHsKICAgICAgICAgICAgICAgIHByaW50Zigi6Z2eIik7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBwcmludGYoIuizquaVuFxuIik7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K

MgozCjQKNQo2CjcKOAo5CjEwCjIxNDc0ODM2NDc=

2
3
4
5
6
7
8
9
10
2147483647