Advertisement
SorahISA

F. 質數家族 (primeconn)

Oct 5th, 2022
601
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxc = 1E7;
  5.  
  6. bitset<maxc> isprime;
  7. vector<int> p;
  8.  
  9. int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;}
  10. int U(int x, int y) {x = R(x), y = R(y); return x ^ y ? p[x] = y, 1 : 0;}
  11.  
  12. int main() {
  13.     ios_base::sync_with_stdio(0), cin.tie(0);
  14.    
  15.     int N; cin >> N;
  16.     if (N == maxc) --N;
  17.    
  18.     p.resize(N+1), iota(begin(p), end(p), 0);
  19.    
  20.     isprime.set();
  21.     isprime[0] = isprime[1] = 0;
  22.     for (int i = 2; i*i <= N; ++i) {
  23.         if (!isprime[i]) continue;
  24.         for (int j = i*i; j <= N; j += i) isprime[j] = 0;
  25.     }
  26.    
  27.     int64_t ans = 0;
  28.     for (int i = 2; i <= N; ++i) {
  29.         if (!isprime[i]) continue;
  30.         // cerr << "isprime: " << i << "\n";
  31.         string num = to_string(i);
  32.         int len = num.size();
  33.         for (int j = len-1, k = 1; j >= 0; --j, k *= 10) {
  34.             for (int d = 1, val = i-k; d <= num[j]-'0'; ++d, val -= k) {
  35.                 if (!j and i >= 10 and num[1] == '0' and d == num[0]-'0') continue;
  36.                 if (isprime[val]) U(i, val); //, cerr << "  " << i << ", " << val << "\n";
  37.             }
  38.         }
  39.         if (R(i) != R(2)) ans += i;
  40.     }
  41.     cout << ans << "\n";
  42.    
  43.     return 0;
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement