Problem 1.6.3 Prime Palindromes

출처: https://train.usaco.org/usacogate

---

문제 설명

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 .

입력 

Line 1: Two integers, a and b

출력 

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

입력 예

5 500

출력 예

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

---

문제 풀이 

자리수가 짝수인 palindrome 은 11의 배수 이므로, 자리수가 홀수인 숫자들을 만들어서 소수인지 검사한다.  다만, 소수는 2를 제외하면 모두 짝수이고, 끝자리가 0/5인 경우도 5의 배수가 된다. 또, 자리수 합이 3의 배수이면 3의 배수가 된다. 이런 몇가지 검사를 통과한 수들을 대상으로 소수검사를 시행한다.

프로그램 내용

#define MIN_A 5
#define MAX_B 100000000

vector <long> palindrome;

bool check_prime(long input);

void palindrome1(int A, int B); /// 1자리 소수 5, 7
void palindrome2(int A, int B); /// 2자리 소수 palindrome 11
void palindrome3(int A, int B); 
void palindrome5(int A, int B);
void palindrome7(int A, int B);
void build_palindrome(int A, int B);

int main() {
    /// build palindrome with digit n
    build_palindrome(A, B);

    sort(palindrome.begin(),palindrome.end(),compare);

    for(int idx=0; idx < palindrome.size();++idx)
        if( palindrome[idx] >= A && palindrome[idx] <= B)
            fout << palindrome[idx] << endl;

 

Chapter 1. Getting started