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
#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
using namespace std;
int t[1000000]; // t[i] == 0 jesli 2*i + 1 jest pierwsza. wielokrotnosci 2 przesiane z definicji. t[] zawiera liczby nieparzyste.

int main()
{
        int i, j, q, p;
        int N = 1000000;
        //printf("%d\n", 2);
        p = 3;  // liczba pierwsza od ktorej przesiewamy
        q = 4;  // miejsce od ktorego przesiewamy dla danego p, t[q] reprezentuje 2*q + 1, czyli 9

        for(i = 1; q < N && i < N; i++)
        {
                if (t[i] == 1)
                {
                        // 2 * i + 1 nie jest pierwsza, idziemy dalej
                        p += 2;
                        q = (p*p -1)>>1;        //(p^2-1)/2
                        continue;
                }
                j = q; t[j] = 1;        // odsiewamy
                while (j + p < N)
                {
                        j += p;
                        t[j] = 1;
                }
                p += 2;
                q = (p*p -1)>>1;
        }
	int last=1;
	// przepisujemy liczby pierwsze do tablicy
	t[0]=2; t[1]=3;last = 2;
	for (int i = 2; i < N;i++)
	{
		if(t[i]==0)
		{
			t[last++]=(i<<1) + 1;
			//cout << (i<<1) + 1<< " ";
		}
	}
	string l;
	cin >> l;
	long long pref,suff;// prefix, suffix
	// ostatna cyfra drugiej liczby
	if (l[l.size()-1]=='0'||(l[l.size()-1]=='2' && l.size()==1) ||l[l.size()-1]=='4'||l[l.size()-1]=='6'||l[l.size()-1]=='8'||l[l.size()-1]=='5')
	{
		cout << "NIE";
		return 0;
	}
	for (int i = 1; i < l.size(); i++)
	{
		if (l[i] == '0'|| \
		   (i-1>0) &&(l[i-1]=='0' || l[i-1]=='2' || l[i-1]=='4'||l[i-1]=='6' || l[i-1]=='8'||l[i-1]=='5') \
		   ) continue;
		stringstream ss;
		ss << l.substr(0,i)<< " " << l.substr(i);
		ss >> pref >> suff;
		if (pref ==1 || suff ==1) continue;
		double pierw=sqrt(pref);
		bool OK=true;
		for (int i=0; t[i] <= pierw && i < last;i++)
		{
			if (pref % t[i] == 0)
			{
				OK=false;
#ifdef DEBUG
cout << pref << "|" << suff << " 1/"<< t[i]<<endl;
#endif
				break;
			}
		}
		if (! OK) continue;
		pierw=sqrt(suff);	
		for (int i=0; t[i] <= pierw && i < last;i++)
                {
                        if (suff % t[i] == 0)
                        {
                                OK=false;
#ifdef DEBUG
cout << pref << "|" << suff << " 2/"<< t[i]<<endl;
#endif
                                break;
                        }
                }
		if (! OK) continue;
		cout << "TAK";
		return 0;
	}
	cout << "NIE";
	return 0;
}