Advertisement
mickypinata

USACO-T019: Prime Palindromes

Nov 28th, 2021
527
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: pprime
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. vector<int> ans;
  11.  
  12. bool isPrime(int x){
  13.     if(x < 2){
  14.         return false;
  15.     }
  16.     int upb = sqrt(x);
  17.     for(int i = 2; i <= upb; ++i){
  18.         if(x % i == 0){
  19.             return false;
  20.         }
  21.     }
  22.     return true;
  23. }
  24.  
  25. string evenPalindrome(string str){
  26.     int sz = str.size();
  27.     for(int i = sz - 1; i >= 0; --i){
  28.         str += str[i];
  29.     }
  30.     return str;
  31. }
  32.  
  33. string oddPalindrome(string str){
  34.     int sz = str.size();
  35.     for(int i = sz - 2; i >= 0; --i){
  36.         str += str[i];
  37.     }
  38.     return str;
  39. }
  40.  
  41. int main(){
  42.     freopen("pprime.in", "r", stdin);
  43.     freopen("pprime.out", "w", stdout);
  44.  
  45.     for(int a = 0; a <= 9; ++a){
  46.         for(int b = 0; b <= 9; ++b){
  47.             for(int c = 0; c <= 9; ++c){
  48.                 for(int d = 0; d <= 9; ++d){
  49.                     string str = to_string(a * 1000 + b * 100 + c * 10 + d);
  50.                     int x = stoi(evenPalindrome(str));
  51.                     if(isPrime(x)){
  52.                         ans.push_back(x);
  53.                     }
  54.                     x = stoi(oddPalindrome(str));
  55.                     if(isPrime(x)){
  56.                         ans.push_back(x);
  57.                     }
  58.                 }
  59.             }
  60.         }
  61.     }
  62.     sort(ans.begin(), ans.end());
  63.     int l, r;
  64.     scanf("%d%d", &l, &r);
  65.     int lwb = lower_bound(ans.begin(), ans.end(), l) - ans.begin();
  66.     int upb = upper_bound(ans.begin(), ans.end(), r) - ans.begin() - 1;
  67.     for(int i = lwb; i <= upb; ++i){
  68.         cout << ans[i] << '\n';
  69.     }
  70.  
  71.     fclose(stdin);
  72.     fclose(stdout);
  73.     return 0;
  74. }
  75.  
Advertisement
RAW Paste Data Copied
Advertisement