USACO 1.5 - Prime Palindromes

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .

PROGRAM NAME: pprime

INPUT FORMAT

Line 1:

Two integers, a and b

SAMPLE INPUT (file pprime.in)

5 500

OUTPUT FORMAT

The list of palindromic primes in numerical order, one per line.

SAMPLE OUTPUT (file pprime.out)

5
7
11
101
131
151
181
191
313
353
373
383

HINTS (use them carefully!)

       HINT 1          HINT 2   

출처: http://train.usaco.org/

두 수 a,b 가 (5 <= a < b <= 100,000,000) 주어질 때, a 와 b 사이에 있는 소수이면서 palindrome 인 수를 출력하시오.

naive 하게 풀 경우 시간 복잡도 문제가 있어 힌트를 참고하여 우선 palindrome 인 수를 구해서 prime 을 검사하는 방법을 사용해 풀었습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
bool isPrime(int n) 
{
    if (n == 1) 
        return false;
    if (n == 2) 
        return true;
 
    if (n % 2 == 0) 
        return false;
 
    int sqrtn = int(sqrt(n));
 
    for (int div = 3; div <= sqrtn; div += 2)
        if (n % div == 0)
            return false;
    return true;
}
 
vector<int> solve(int min, int max)
{
    vector<int> ret;
    if (min <= 5 && max >= 5)
        ret.push_back(5);
    if (min <= 7 && max >= 7)
        ret.push_back(7);
 
    if (max < 11)
        return ret;
    for (int d1 = 1; d1 <= 9; d1 += 2)
    {
        int palindrome = 10 * d1 + d1;
        if (isPrime(palindrome))
            ret.push_back(palindrome);
    }
 
    if (max < 101)
        return ret;
    for (int d1 = 1; d1 <= 9; d1 += 2)
    {
        for (int d2 = 0; d2 <= 9; d2++)
        {
            int palindrome = 100 * d1 + 10 * d2 + d1;
            if (isPrime(palindrome))
                ret.push_back(palindrome);
 
            palindrome = 1000 * d1 + 100 * d2 + 10 * d2 + d1;
            if (isPrime(palindrome))
                ret.push_back(palindrome);
        }
    }
 
    if (max < 10001)
        return ret;
    for (int d1 = 1; d1 <= 9; d1 += 2)
    {    
        for (int d2 = 0; d2 <= 9; d2++) 
        {
            for (int d3 = 0; d3 <= 9; d3++) 
            {
                int palindrome = 10000 * d1 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;
                if (isPrime(palindrome))
                    ret.push_back(palindrome);
 
                palindrome = 100000 * d1 + 10000 * d2 + 1000 * d3 + 100 * d3 + 10 * d2 + d1;
                if (isPrime(palindrome))
                    ret.push_back(palindrome);
            }
        }
    }
 
    if (max < 1000001)
        return ret;
    for (int d1 = 1; d1 <= 9; d1 += 2)
    {
        for (int d2 = 0; d2 <= 9; d2++)
        {
            for (int d3 = 0; d3 <= 9; d3++)
            {
                for (int d4 = 0; d4 <= 9; d4++)
                {
                    int palindrome = 1000000 * d1 + 100000 * d2 + 10000 * d3 + 1000 * d4 + 100 * d3 + 10 * d2 + d1;
                    if (isPrime(palindrome))
                        ret.push_back(palindrome);
 
                    palindrome = 10000000 * d1 + 1000000 * d2 + 100000 * d3 + 10000 * d4 + 1000 * d4 + 100 * d3 + 10 * d2 + d1;
                    if (isPrime(palindrome))
                        ret.push_back(palindrome);
                }
            }
        }
    }
 
    sort(ret.begin(), ret.end());
    return ret;
}
 
int main()
{
    ifstream fin("pprime.in");
    ofstream fout("pprime.out");
 
    int a, b;
    fin >> a >> b;
 
    vector<int> ret = solve(a, b);
    
    for (vector<int>::iterator it = ret.begin(); it != ret.end(); it++)
    {
        if (*it > b)
            break;
        if (*it >= a)
            fout << *it << endl;
    }
 
    fin.close();
    fout.close();
    return 0;
}