[Algorithm] Baekjoon 1747번 : 소수&팰린드롬

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

int n;
 
bool isPrimeNum(int n)
{
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0) return false;
    }
 
    return true;
}
 
bool isPalindrome(int n)
{
    string s = to_string(n);
    int size = s.size();
    int halfSize = s.size() / 2;
 
    for (int i = 0; i < halfSize; ++i)
    {
        if (s[i] != s[size - 1 - i]) return false;
    }
 
    return true;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    if (n == 1) ++n;
 
    while (1)
    {
        if (isPrimeNum(n) && isPalindrome(n)) break;
        ++n;
    }
 
    cout << n;
}

 

소수검사를 어떻게하냐에 따라 시간효율이 극명하게 나뉜다.

단순히 저렇게 숫자하나하나 일일이 검사해도 통과는 한다.

다만, 이런 문제같이 여러숫자를 소수인지 판별할 때는 에라토스테네스의 체를 이용하는게 훨씬 빠르다.

 

#define MAX 1005000
 
bool checkPrime[MAX + 1] = { false };
int n;
 
void sieve()
{
    checkPrime[1] = true;
 
    for (int i = 2; i * i <= MAX; ++i)
    {
        if (checkPrime[i]) continue;
 
        for (int j = i * i; j <= MAX; j += i)
        {
            checkPrime[j] = true;
        }
    }
}
 
bool isPalindrome(int n)
{
    string s = to_string(n);
    int size = s.size();
    int halfSize = s.size() / 2;
 
    for (int i = 0; i < halfSize; ++i)
    {
        if (s[i] != s[size - 1 - i]) return false;
    }
 
    return true;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    sieve();
 
    while (1)
    {
        if (!checkPrime[n] && isPalindrome(n)) break;
        ++n;
    }
 
    cout << n;
}