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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int pierwsze_w_parach[20];

const int PIERWSZE_SIZE = 1000 * 1000 + 17;
bool pierwsza[PIERWSZE_SIZE];

int main()
{
    long long n;
    scanf("%lld", &n);
    vector<pair<long long,int> > v;
    long long pot10=10, nr_pary=1, tmpdiv, tmpmod;
    while (pot10 < n) {
        tmpdiv = n / pot10;
        tmpmod = n % pot10;
        if (tmpdiv % 10 != 0 && tmpmod * 10 > pot10) {
            v.push_back(make_pair(n / pot10, nr_pary));
            v.push_back(make_pair(n % pot10, nr_pary));
        }
        pot10 *= 10;
        ++nr_pary;
    }

    if (v.size() == 0) {
        printf("NIE\n");
        return 0;
    }

    bool wynik = false;
    sort(v.begin(), v.end());

    long long limit = v.back().first;
    if (limit < PIERWSZE_SIZE && limit * limit < PIERWSZE_SIZE)
        limit *= limit; // just omit corner cases
    for (int i = 0; i < PIERWSZE_SIZE; ++i)
        pierwsza[i] = true;
    vector<int> pierwsze;
    for (long long i = 2; i * i <= limit; ++i)
        if (pierwsza[i]) {
            pierwsze.push_back(i);
            for (long long j = 2 * i; j * j <= limit; j += i)
                pierwsza[j] = false;
        }

    for (int i = 0; !wynik && i < v.size(); ++i) {
        long long curr = v[i].first;
        if (curr * curr <= limit) {
            if (pierwsza[curr]) {
                ++pierwsze_w_parach[v[i].second];
                //fprintf(stderr, "OK: (%lld, %d)\n", curr, v[i].second);
                if (pierwsze_w_parach[v[i].second] == 2)
                    wynik = true;
            }
            // else: nie jest pierwsza
        } else {
            int p = 2;
            for (auto it = pierwsze.begin(); it != pierwsze.end() && *it * *it <= curr && curr % p != 0; ++it)
                p = *it;
            if (curr % p != 0) {
                ++pierwsze_w_parach[v[i].second];
                //fprintf(stderr, "OK: (%lld, %d)\n", curr, v[i].second);
                if (pierwsze_w_parach[v[i].second] == 2)
                    wynik = true;
            }
        }
    }

    printf("%s\n", (wynik ? "TAK" : "NIE"));

    return 0;
}