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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>

typedef long long lLong;
typedef unsigned long uLong;
typedef unsigned long long ulLong;
typedef unsigned int uInt;
typedef unsigned char Byte;

using namespace std;

#define FOR(x, b, e) for(int x=b; x<=(e); ++x)
#define ALL(i) (i).begin(), (i).end()
#define CONTAINS(i,v) (find(ALL(i),v)!=(i).end())
typedef vector<bool> bit_vector;
typedef vector<ulLong> VI;
typedef vector<ulLong> VLL;

// Funkcje realizuje algorytm sita Eratostenesa oraz sprawdzajace czy liczba jest pierwsza
// zaczerpniete z: Piotr Stanczyk Nr albumu: 209291 Algorytmika praktyczna w konkursach Informatycznych


// Funkcja przeprowadza test Millera-Rabina dla liczby x przy podstawie n
bool PWit(lLong x, lLong n)
{
	if (x >= n) return 0;
	lLong d = 1, y;
	lLong t = 0, l = n - 1;
	while (!(l & 1))
	{
		++t;
		l >>= 1;
	}
	for (; l > 0 || t--; l >>= 1) {
		if (l & 1) d = (d * x) % n;
		if (!l)
		{
			x = d;
			l = -1;
		}
		y = (x * x) % n;
		// Jesli test Millera wykryl, ze liczba nie jest pierwsza, to zwroc prawde
		if (y == 1 && x != 1 && x != n - 1) return 1;
		x = y;
	}
	return x != 1;
}

bool IsPrime(lLong x) {
	return !(x < 2 || PWit(2, x) || PWit(3, x) || PWit(5, x) || PWit(7, x));
}

class PrzypadekTestowy
{
private:	
	lLong _liczba;
	inline void Reset()
	{	
		_liczba = 0;
	}

	inline void WczytajWspolczynniki(FILE *input)
	{		
		fscanf(input, "%lld\n", &_liczba);
	}

public:
	
	inline void WczytajPrzypadekTestowy()
	{
		WczytajPrzypadekTestowy(stdin);
	}
	inline void WczytajPrzypadekTestowy(FILE *input)
	{
		Reset();		
		WczytajWspolczynniki(input);		
	}

	inline void Rozwiaz()
	{	
		lLong l2=0;
		bool czyDruga = false;		
		lLong posPow = 1;

		while (_liczba > 0)
		{
			int rd = _liczba % 10; //utnij ostatnia cyfre
			_liczba = (_liczba - rd) / 10;	
			if (_liczba == 0) break;
			l2 += posPow *rd; //doklej ucieta cyfre na poczatek drugiej liczby
			posPow *= 10;
			if (rd == 0) continue; //jest zero wiodace wiec nie testujemy
			if (IsPrime(_liczba) && IsPrime(l2)) //jesli obie pierwsze, to liczba jest druga
			{
				czyDruga = true;
				break;
			}
		}
		printf("%s\n", czyDruga ? "TAK" : "NIE");
	}	
};

int main(int argc, char **argv)
{	
	FILE *in = stdin;
	if (argc>1)
	{
		in = fopen(argv[1], "rt");
		if (NULL == in)
		{
			in = stdin;
		}
	}
	PrzypadekTestowy p;
	p.WczytajPrzypadekTestowy(in);
	p.Rozwiaz();	
	return 0;
}