Advertisement
Josif_tepe

Untitled

Oct 10th, 2021
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. bool prime[1000005];
  7. bool visited[1000005];
  8. int main() {
  9.     long long million = 1e6;
  10.     for(int i = 0; i <= million; i++) {
  11.         prime[i] = true;
  12.         visited[i] = false;
  13.     }
  14.     prime[0] = false;
  15.     prime[1] = false;
  16.    
  17.     for(long long i = 2; i <= million; i++) {
  18.         if(prime[i]) {
  19.             for(long long j = i * i; j <= million; j += i) {
  20.                 prime[j] = false;
  21.             }
  22.         }
  23.     }
  24.     string s;
  25.     cin >> s;
  26.     int primes = 0;
  27.     for(int i = 0; i < (int) s.size(); i++) {
  28.         string tmp = "";
  29.         for(int j = i; j < i + 6 and j < (int) s.size(); j++) {
  30.             tmp += s[j];
  31.             int x = 0;
  32.             for(int k = 0; k < (int) tmp.size(); k++) {
  33.                 x = (x * 10) + (tmp[k] - '0');
  34.             }
  35.             if(prime[x] and !visited[x]) {
  36.                 visited[x] = true;
  37.                 primes++;
  38.             }
  39.         }
  40.     }
  41.     cout << primes << endl;
  42.     return 0;
  43. }
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement