[BOJ/C++] 백준 1747번: 소수&팰린드롬

 

🔗 문제 링크 : https://www.acmicpc.net/problem/1747

 

---

 

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

 

 

 

 

입출력 예시

입력

첫째 줄에 N이 주어진다.

 

 

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

 

 

 

입출력 예시

 

 

 

---

 

풀이 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int N;
    cin >> N;

    int n = N - 1;
    while (1)
    {
        n++;
        if (n < 2) continue;
        bool isDecimal = true;
        bool isPalindrome = true;

        /* 소수 판별 */
        for (int i = 2; i * i <= n; i++) {
            if (n == 2) break;
            if (n % i == 0) {
                isDecimal = false;
                break;
            }
        }
        if (!isDecimal) continue;      

        /* 팰린드롬 판별 */
        string str = to_string(n);
        string::iterator it = str.begin();
        string::reverse_iterator rit = str.rbegin();
        for (int i = 0; i < str.size(); i++) {
            if (*it != *rit) {
                isPalindrome = false;
                break;
            }
            it++; rit++;
        }
        if (!isPalindrome) continue;  
        
        cout << n;
        return 0;
    }
}

 

 

⭐ 중요한 테스트 케이스

입력	출력
1	2
2	2
4	5
1000000	1003001

 

• 1은 소수가 아니다.
• 채점 중 70%정도에 틀리는 경우에는 4를 입력하는 테스트케이스를 확인해보자.
  • 위 코드 20번째 줄의 i * i <= n을 i * i < n 으로 작성했을 때의 문제였다.

 

---