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
/*
 * Michał Zagórski (C) 2017
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

const char* yes = "TAK";
const char* no = "NIE";
#define div_count 13

struct check_entry {
    unsigned long long int n;
    int prime;
    int checked;
};

struct check_entry left_div[div_count];
struct check_entry right_div[div_count];
unsigned int size = 0;
unsigned long long int the_biggest;
inline void count_primes();
inline int check_primes();

int main()
{
    unsigned long long int number;
    unsigned int index = 0;
    if (scanf("%llu", &number) < 0) {
    	return EXIT_FAILURE;
    }
    unsigned long long int divider = 10;
    unsigned long long int left, right;
    while (divider < number) {
        left = number / divider;
        right = number % divider;
        left_div[index].n = left;
        left_div[index].prime = 1;
        left_div[index].checked = 0;
        /*
         * When the right number has zeros on begin it is smaller than 1/10
         * of divider => Invalid split of number excusing it from check.
         */
        if (right < divider / 10) {
        	right_div[index].n = right;
        	right_div[index].prime = 0;
        	right_div[index].checked = 1;
        } else {
        	right_div[index].n = right;
        	right_div[index].prime = 1;
        	right_div[index].checked = 0;
        	index++;
    	}
        divider *= 10;
    }
    the_biggest = left_div[0].n;
    if (the_biggest < right_div[index - 1].n) {
        the_biggest = right_div[index - 1].n;
    }
    size = index;
    count_primes();
    printf("%s\n", (check_primes() > 0) ? yes : no);
    return 0;
}

inline void basic_check(struct check_entry* entry);
inline void check_num(struct check_entry* entry, unsigned long long int d);
inline void count_primes() 
{
    unsigned long long int div = 2;
    for(unsigned int i = 0; i < size; i++) {
    	basic_check(&left_div[i]);
    	basic_check(&right_div[i]);
    }
    for(div = 5; div * div <= the_biggest; div += 2) {
    	for (unsigned int i = 0; i < size; i++) {
    		check_num(&left_div[i], div);
    		check_num(&right_div[i], div);
    	} 
    }
}




inline void basic_check(struct check_entry* entry) {
        if(entry->n < 2) {
            entry->checked = 1;
            entry->prime = 0;
        } else if (entry->n < 4) {
            entry->checked = 1;
            entry->prime = 1;
        } else if (entry->n % 2 == 0 || entry->n % 3 == 0) {
        	entry->checked = 1;
        	entry->prime = 0;
        }
}

inline void check_num(struct check_entry* entry, unsigned long long int d) {
	if (entry->checked == 1)
		return;
	if (entry->n < d) {
		entry->checked = 1;
		return;
	}
	if (entry->n % d == 0) {
		entry->prime = 0;
		entry->checked = 1;
	}
}

inline int check_primes() {
	for (unsigned int i = 0; i < size; i++) {
		if(left_div[i].prime == 1 && right_div[i].prime == 1) {
			//fprintf(stderr, "%llu | %llu\n", left_div[i].n, right_div[i].n);
			return 1;
		}
	}
	return 0;
}