[백준] 1990번 : 소수인팰린드롬 (C++)

1990번 : 소수인팰린드롬

---

문제)

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오.

 

 

 

입력 :

입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다.

 

 

 

 

출력 :

첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다.

 

 

 

 

 

풀이)

 

// 1990. 소수인팰린드롬
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int a, b;
bool check_prime(int a)
{
    if (a == 1) return false;
 
    for (int i = 2; i * i <= a; i++)
    {
        if (a % i == 0) return false;
    }
    return true;
}
 
bool check_pailn(int a)
{
    string a1 = to_string(a);
    string a2 = a1;
    reverse(a2.begin(), a2.end());
    
    return a1 == a2;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> a >> b;
 
    // 이 문제의 핵심.
    // 소수이면서 팰린드롬인 숫자는 최댓값이 1000만을 넘지 않는다.
    if (b >= 10000000) b = 10000001;
 
    for (int i = a; i < b + 1; i++)
    {
        if (check_pailn(i) && check_prime(i))
        {
            cout << i << "\n";
        }
    }
 
    cout << -1;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/1990 

1990번: 소수인팰린드롬