Advertisement
mickypinata

USACO-T020: Super Prime Rib

Nov 28th, 2021
484
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: sprime
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. vector<int> ans;
  11. int n;
  12.  
  13. bool isPrime(int x){
  14.     if(x < 2){
  15.         return false;
  16.     }
  17.     int upb = sqrt(x);
  18.     for(int i = 2; i <= upb; ++i){
  19.         if(x % i == 0){
  20.             return false;
  21.         }
  22.     }
  23.     return true;
  24. }
  25.  
  26. void recur(int d, int x){
  27.     if(d > n){
  28.         ans.push_back(x);
  29.         return;
  30.     }
  31.     for(int i = 0; i <= 9; ++i){
  32.         int newX = 10 * x + i;
  33.         if(isPrime(newX)){
  34.             recur(d + 1, newX);
  35.         }
  36.     }
  37. }
  38.  
  39. int main(){
  40.     freopen("sprime.in", "r", stdin);
  41.     freopen("sprime.out", "w", stdout);
  42.  
  43.     scanf("%d", &n);
  44.     recur(1, 0);
  45.     sort(ans.begin(), ans.end());
  46.     for(int x : ans){
  47.         cout << x << '\n';
  48.     }
  49.  
  50.     fclose(stdin);
  51.     fclose(stdout);
  52.     return 0;
  53. }
  54.  
Advertisement
RAW Paste Data Copied
Advertisement