SHARE
TWEET

Untitled

a guest Oct 21st, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. bool check[10000000];
  9. vector<int> totalset;
  10.  
  11. void go(int cnt, int num, const vector<int> &idx) {
  12.     if (cnt == idx.size()) {
  13.         if (num != 0) {
  14.             totalset.push_back(num);
  15.         }
  16.         return;
  17.     }
  18.  
  19.     go(cnt + 1, num, idx);
  20.     if (!(num == 0 && idx[cnt] == 0)) {
  21.         go(cnt + 1, num * 10 + idx[cnt], idx);
  22.     }
  23.     return;
  24. }
  25.  
  26. int solution(string numbers) {
  27.     string s = numbers;
  28.     vector<int> idx;
  29.     for (int i = 0; i < s.size(); i++) {
  30.         int num = s[i] - '0';
  31.         idx.push_back(num);
  32.     }
  33.  
  34.     sort(idx.begin(), idx.end());
  35.     do {
  36.         go(0, 0, idx);
  37.     } while (next_permutation(idx.begin(), idx.end()));
  38.  
  39.     sort(totalset.begin(), totalset.end());
  40.     totalset.erase(unique(totalset.begin(), totalset.end()), totalset.end());
  41.    
  42.     memset(check, true, sizeof(check));
  43.     check[1] = false;
  44.     for (int i = 2; i * i < 10000000; i++) {
  45.         if (!check[i]) continue;
  46.         for (int j = i + i; j < 10000000; j += i) {
  47.             check[j] = false;
  48.         }
  49.     }
  50.    
  51.     int ans = 0;
  52.     for (int i = 0; i < totalset.size(); i++) {
  53.         if (check[totalset[i]]) {
  54.             ans += 1;
  55.         }
  56.     }
  57.    
  58.     return ans;
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top