USACO-T019: Prime Palindromes

/*
ID: mickyta1
TASK: pprime
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

vector<int> ans;

bool isPrime(int x){
    if(x < 2){
        return false;
    }
    int upb = sqrt(x);
    for(int i = 2; i <= upb; ++i){
        if(x % i == 0){
            return false;
        }
    }
    return true;
}

string evenPalindrome(string str){
    int sz = str.size();
    for(int i = sz - 1; i >= 0; --i){
        str += str[i];
    }
    return str;
}

string oddPalindrome(string str){
    int sz = str.size();
    for(int i = sz - 2; i >= 0; --i){
        str += str[i];
    }
    return str;
}

int main(){
    freopen("pprime.in", "r", stdin);
    freopen("pprime.out", "w", stdout);

    for(int a = 0; a <= 9; ++a){
        for(int b = 0; b <= 9; ++b){
            for(int c = 0; c <= 9; ++c){
                for(int d = 0; d <= 9; ++d){
                    string str = to_string(a * 1000 + b * 100 + c * 10 + d);
                    int x = stoi(evenPalindrome(str));
                    if(isPrime(x)){
                        ans.push_back(x);
                    }
                    x = stoi(oddPalindrome(str));
                    if(isPrime(x)){
                        ans.push_back(x);
                    }
                }
            }
        }
    }
    sort(ans.begin(), ans.end());
    int l, r;
    scanf("%d%d", &l, &r);
    int lwb = lower_bound(ans.begin(), ans.end(), l) - ans.begin();
    int upb = upper_bound(ans.begin(), ans.end(), r) - ans.begin() - 1;
    for(int i = lwb; i <= upb; ++i){
        cout << ans[i] << '\n';
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}