[백준][C++] #1990 소수인팰린드롬

 

 

문제 #1990

 

시간 제한 1초

메모리 제한 256MB

 

 

 

 

해당 문제는 두 수를 입력받아 그 수 사이에 있는 소수이면서 팰린드롬인 수를 출력해야 합니다.

이 문제 해결하기 위해 두 함수를 작성하였는데, 시간초과가 나왔습니다.

친구가 추천해준 문제라, 풀었냐는 말에 시간초과로 못 풀었다 대답하니 소수이면서 팰린드롬인 수는 10,000,000부터 100,000,000까지 없다고 이른바 팁이라고 알려준 것이 기억났습니다. 다른 사람들은 어떻게 문제를 해결하였는지 구글링을 하였고, 다른 사람도 반복문에서 10,000,000 까지 소수이면서 팰린드롬인 수를 검색하되 사용자가 입력한 수가 나왔을 경우 반복문을 빠져나오는 방식을 사용한 것을 알게되었습니다.

저도 이와 같이 작성하였더니 이 문제 풀이에서 마주한 시간초과 문제를 해결할 수 있었습니다.

 

이후, 이전에 작성한 코드를 수정하여 2부터 100,000,000까지 수 중에서 소수이면서 팰린드롬인 수가 몇까지 있는지 검사해보는 코드를 작성해보고 그 수를 확인해보고자 하였습니다.

작성한 코드

#include <iostream>
#include <string>
using namespace std;
bool isPrime(int num);
bool isPalindrome(string num);
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 2; i <= 100000000; ++i)
    {
        if (isPrime(i) && isPalindrome(to_string(i))) // 소수이면서 팰린드롬인 수를 판단
            // if (isPrime(i)) // 소수만 판단
            cout << i << "\n";
    }

    return 0;
}
bool isPrime(int num)
{
    for (int i = 2; i * i <= num; ++i)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
bool isPalindrome(string num)
{
    string reversedNum = num;
    reverse(reversedNum.begin(), reversedNum.end());
    if (num == reversedNum)
        return true;
    return false;
}

아래는 1억까지 소수이면서 팰린드롬인 수와 소수를 출력해본 결과다.

좌) 소수이면서 팰린드롬인 수 / 우) 소수

문제 해결을 위한 코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int st, en;
bool isPrime(int num)
{
    if (num < 2)
        return false;
    for (int i = 2; i * i <= num; ++i)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
bool isPal(int num)
{
    string temp = to_string(num);
    string front = temp;
    reverse(temp.begin(), temp.end());
    string back = temp;
    if (front != back)
        return false;
    return true;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> st >> en;
    for (int i = st; i <= 10000000; ++i)
    {

        if (isPal(i) && isPrime(i))
            cout << i << "\n";
        if (i == en)
            break;
    }
    cout << "-1\n";

    return 0;
}