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
#include <array>
#include <iostream>

class {
    typedef uint64_t u64;
    typedef uint64_t s64;

    s64 MultiplyMod(s64 a, s64 b, s64 mod) { //computes a * b % mod
        u64 r = 0;
        a %= mod, b %= mod;
        while (b) {
            if (b & 1)
                r = (r + a) % mod;
            b >>= 1, a = ((u64) 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) { // deterministic Miller-Rabbin
                        // determines if n is a prime number
        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 run() {
        std::cin >> std::ws;

        // no leading zeroes
        if (std::cin.peek() == '0')
            return false;

        std::cin >> num;

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

        u64 leftpart = 0, rightpart, leftcheck;

        for (u64 pow10 = 1; pow10 < num; pow10 *= 10) {
            leftcheck = leftpart;

            leftpart = num / pow10;
            rightpart = num - (leftpart * pow10);

            // detect and omit leading zeroes
            if (leftcheck == (leftcheck / 10) * 10)
                continue;

            if (isprime<u64>(rightpart) && isprime<u64>(leftpart))
                return true;
        }
        return false;
    }

    u64 num;
} m;

int main() { std::cout << (m.run() ? "TAK" : "NIE"); };