#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pows[70];
void fil() {
    pows[0] = 1ll;
    for (int i = 1; i <= 63; ++i)
        pows[i] = pows[i - 1] * 2ll;
}
ll powm(ll p, ll n, ll mod) {
    if (n == 0)
        return 1ll;
    if (n == 1)
        return p % mod;
    if (!(n & 1)) {
        ll step = powm(p, n / 2, mod);
        return (step * step) % mod;
    }
    else {
        ll step = powm(p, (n - 1) / 2, mod);
        return (((step * step) % mod) * p) % mod;
    }
}
bool mrt(ll p) {
    if (p == 1)
        return false;
    ll s = 0, d = p - 1;
    while (!(d & 1)) {
        d = d / 2;
        s++;
    }
    srand(time(NULL)); /// Генерируем действительно случайные и разные a
    for (int i = 1; i <= 5; ++i) { /// Те самые 5 проверок
        ll a = rand() % p;
        if (a == 0)
            a++;
        bool flag1 = false, flag2 = false;
        if (powm(a % p, d, p) == 1) /// Первая проверка
            flag1 = true;
        if (!flag1)
            for (int r = 0; r < s; ++r) /// Вторая проверка
                if (powm(a % p, pows[r] * d, p) == p - 1)
                    flag2 = true;
        if (!flag1 && !flag2)
            return false;
    }
    return true;
}

int main() {
    ll p;
    fil();
    cin >> p;
    if (mrt(p))
        cout << "True";
    else
        cout << "False";
}