#include <iostream>

using namespace std;

int main() {

    int n;

    cin >> n;

    bool isPrime = true;

    if (n < 2) {

        isPrime = false;

    } else if (n == 2) {

        isPrime = true;

    } else if (n % 2 == 0) {

        isPrime = false;

    } else {

        for (int i = 3; i * i <= n; i += 2) {

            if (n % i == 0) {

                isPrime = false;

                break;

            }

        }

    }

    if (isPrime) {

        cout << n << " is a prime number" << endl;

    } else {

        cout << n << " is not a prime number" << endl;

    }

    return 0;

}