F. 質數家族 (primeconn)

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

const int maxc = 1E7;

bitset<maxc> isprime;
vector<int> p;

int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;}
int U(int x, int y) {x = R(x), y = R(y); return x ^ y ? p[x] = y, 1 : 0;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N; cin >> N;
    if (N == maxc) --N;

    p.resize(N+1), iota(begin(p), end(p), 0);

    isprime.set();
    isprime[0] = isprime[1] = 0;
    for (int i = 2; i*i <= N; ++i) {
        if (!isprime[i]) continue;
        for (int j = i*i; j <= N; j += i) isprime[j] = 0;
    }

    int64_t ans = 0;
    for (int i = 2; i <= N; ++i) {
        if (!isprime[i]) continue;
        // cerr << "isprime: " << i << "\n";
        string num = to_string(i);
        int len = num.size();
        for (int j = len-1, k = 1; j >= 0; --j, k *= 10) {
            for (int d = 1, val = i-k; d <= num[j]-'0'; ++d, val -= k) {
                if (!j and i >= 10 and num[1] == '0' and d == num[0]-'0') continue;
                if (isprime[val]) U(i, val); //, cerr << "  " << i << ", " << val << "\n";
            }
        }
        if (R(i) != R(2)) ans += i;
    }
    cout << ans << "\n";

    return 0;
}