#include <iostream> #include <algorithm> using namespace std; #define MAX_PRIMES 227646 long long primes[MAX_PRIMES]; #define MAX_CHECK 3162277 bool checkPrime[MAX_CHECK]; int numberOfPrimes = 8; long long tenToThePowerOf(int exp) { switch (exp) { case 0: return 1; case 1: return 10; case 2: return 100; case 3: return 1000; case 4: return 10000; case 5: return 100000; case 6: return 1000000; case 7: return 10000000; case 8: return 100000000; case 9: return 1000000000; case 10: return 10000000000; case 11: return 100000000000; case 12: return 1000000000000; } } void generatePrimes() { for (int i = 2; i < MAX_CHECK; ++i) { checkPrime[i] = true; } for (int candidate = 2; candidate < MAX_CHECK; ++candidate) { if(!checkPrime[candidate]) continue; for (int multiple = 2*candidate; multiple < MAX_CHECK; multiple += candidate) { checkPrime[multiple] = false; } } numberOfPrimes = 0; for (int j = 0; j < MAX_CHECK; ++j) { if(checkPrime[j]) { primes[numberOfPrimes] = j; numberOfPrimes++; } } } std::pair<long long, long long> splitNumber(long long number, int place) { std::pair<long long, long long> pair; //place >= 1 && place < 13 pair.first = number % tenToThePowerOf(place); pair.second = number / tenToThePowerOf(place); return pair; } bool isPrime(long long n, long long primePool[], int poolSize) { if(binary_search(primePool, primePool+poolSize, n)) return true; for(auto i = 0; i < poolSize; i++) { if(n % primePool[i] == 0) return false; } return true; } bool isGood(long long number) { for (int place = 1; place < 13; ++place) { auto split = splitNumber(number, place); if(split.first == 0 || split.second == 0) continue; if(split.second < tenToThePowerOf(place-1)) continue; if( isPrime(split.first, primes, numberOfPrimes) && isPrime(split.second, primes, numberOfPrimes) ) { return true; } } return false; } int main(int argc, char **argv) { std::ios_base::sync_with_stdio(false); long long n; cin >> n; generatePrimes(); if(isGood(n)) { cout << "TAK"; } else { cout << "NIE"; } return 0; }
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 | #include <iostream> #include <algorithm> using namespace std; #define MAX_PRIMES 227646 long long primes[MAX_PRIMES]; #define MAX_CHECK 3162277 bool checkPrime[MAX_CHECK]; int numberOfPrimes = 8; long long tenToThePowerOf(int exp) { switch (exp) { case 0: return 1; case 1: return 10; case 2: return 100; case 3: return 1000; case 4: return 10000; case 5: return 100000; case 6: return 1000000; case 7: return 10000000; case 8: return 100000000; case 9: return 1000000000; case 10: return 10000000000; case 11: return 100000000000; case 12: return 1000000000000; } } void generatePrimes() { for (int i = 2; i < MAX_CHECK; ++i) { checkPrime[i] = true; } for (int candidate = 2; candidate < MAX_CHECK; ++candidate) { if(!checkPrime[candidate]) continue; for (int multiple = 2*candidate; multiple < MAX_CHECK; multiple += candidate) { checkPrime[multiple] = false; } } numberOfPrimes = 0; for (int j = 0; j < MAX_CHECK; ++j) { if(checkPrime[j]) { primes[numberOfPrimes] = j; numberOfPrimes++; } } } std::pair<long long, long long> splitNumber(long long number, int place) { std::pair<long long, long long> pair; //place >= 1 && place < 13 pair.first = number % tenToThePowerOf(place); pair.second = number / tenToThePowerOf(place); return pair; } bool isPrime(long long n, long long primePool[], int poolSize) { if(binary_search(primePool, primePool+poolSize, n)) return true; for(auto i = 0; i < poolSize; i++) { if(n % primePool[i] == 0) return false; } return true; } bool isGood(long long number) { for (int place = 1; place < 13; ++place) { auto split = splitNumber(number, place); if(split.first == 0 || split.second == 0) continue; if(split.second < tenToThePowerOf(place-1)) continue; if( isPrime(split.first, primes, numberOfPrimes) && isPrime(split.second, primes, numberOfPrimes) ) { return true; } } return false; } int main(int argc, char **argv) { std::ios_base::sync_with_stdio(false); long long n; cin >> n; generatePrimes(); if(isGood(n)) { cout << "TAK"; } else { cout << "NIE"; } return 0; } |