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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>

using namespace std;

class {

    long long MultiplyMod(long long int a, long long int b, long long int mod) { //computes a * b % mod
        long long int r = 0;
        a %= mod, b %= mod;
        while (b) {
            if (b & 1)
                r = (r + a) % mod;
            b >>= 1, a = ((long long int) a << 1) % mod;
        }
        return r;
    }

    template<typename T>
    T PowerMod(T a, T n, T mod) { // computes a^n % mod
        T r = 1;
        while (n) {
            if (n & 1)
                r = MultiplyMod(r, a, mod);
            n >>= 1, a = MultiplyMod(a, a, mod);
        }
        return r;
    }

    template<typename T>
    bool isprime(T n) { //  Miller-Rabbin
                        // sprawdza czy n jest liczba pierwsza
        const int pn = 9, p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
        for (int i = 0; i < pn; ++i)
            if (n % p[i] == 0)
                return n == p[i];
        if (n < p[pn - 1])
            return 0;
        T s = 0, t = n - 1;
        while (~t & 1)
            t >>= 1, ++s;
        for (int i = 0; i < pn; ++i) {
            T pt = PowerMod<T>(p[i], t, n);
            if (pt == 1)
                continue;
            bool ok = 0;
            for (int j = 0; j < s && !ok; ++j) {
                if (pt == n - 1)
                    ok = 1;
                pt = MultiplyMod(pt, pt, n);
            }
            if (!ok)
                return 0;
        }
        return 1;
    }
      public:
    bool sprawdz() {
        cin >> ws;

        // bez wiodacych zer
        if (cin.peek() == '0')
            return false;

        cin >> numer;

        /////////////////////////////////////////////////////////////

        long long int lewaczesc = 0, prawaczesc, lewospraw;

        for (long long int pow10 = 1; pow10 < numer; pow10 *= 10) {
            lewospraw = lewaczesc;

            lewaczesc = numer / pow10;
            prawaczesc = numer - (lewaczesc * pow10);

            // wykryj i omin wiodace zera
            if (lewospraw == (lewospraw / 10) * 10)
                continue;

            if (isprime<long long int>(prawaczesc) && isprime<long long int>(lewaczesc))
                return true;
        }
        return false;
    }

    long long int numer;
} k;

int main()
{
    cout << (k.sprawdz() ? "TAK" : "NIE");




    return 0;
}