Tarifa (државен '17) za 12/15

#include <bits/stdc++.h>
using namespace std;

int main() {
//    std::ios::sync_with_stdio(false);
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    string s;
    cin >> s;
    int len = s.length();
    int n = len < 7 ? stoi(s) : 1000000;
    bitset<1000000> prime;
    bitset<1000000> done;
    prime.set();
    {
        prime[1] = false;
        //for (int i = 4; i <= n; i += 2) prime[i] = false;
        //for (int i = 6; i <= n; i += 3) prime[i] = false;
        for (int p0 = 6; p0*p0 <= n; p0 += 6) {
            int p = p0-1;
            if (prime[p]) {
                for (int i = p*2; i <= n; i += p) {
                    prime[i] = false;
                }
            }
            p = p0 + 1;
            if (prime[p]) {
                for (int i = p*2; i <= n; i += p) {
                    prime[i] = false;
                }
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < len; ++i) {
        int jmax = len-i < 7 ? len-i : 6;
        for (int j = 0; j < jmax; ++j) {
            int x = stoi(s.substr(i, j+1));
            if (!((x > 2 && x%2 == 0) || (x > 3 && x%3 == 0))) {
                if (prime[x] && !done[x]) {
                    done[x] = true;
                    cnt++;
                }
            }
        }
    }
    cout << cnt << endl;
}