[BOJ] 1747 : 소수 & 팰린드롬

문제 : www.acmicpc.net/problem/1747

---

에라토스테네스체

[ 알고리즘풀이 ]

 

 N에서 시작해 소수이면서 팰린드롬인 숫자를 찾을 때까지 N보다 크거나 같은 수를 순회한다. 

 1) 소수인지 체크

 : 에라토스테네스 체를 이용해 입력 최댓값인 100만 보다 넉넉히 큰 1000만까지 소수를 다 구해놓는다.

 --> 입력 최대값인 100만을 입력했을 때 정답이 100,3001 이므로 1000만까지 안 해도 됐었다...!!

 

 2) 팰린드롬인지 체크

 : 숫자의 각 자리를 추출해서 vector에 담아두고 팰린드롬인지 체크하면 된다.

 

[ 코드구현 C++ ]

#include<iostream>
#include<vector>
 
using namespace std;
 
bool isPrime[10000001];
 
void eratos() {
    isPrime[0] = isPrime[1] = true;
    for (int i = 2; i <= 10000000; i++) {
        if (!isPrime[i]) {
            for (int j = 2 * i; j <= 10000000; j += i)
                isPrime[j] = true;
        }
    }
}
 
bool isPalindrome(int x) {
    vector<int> numbers;
    while (x) {
        numbers.push_back(x % 10);
        x /= 10;
    }
    bool ans = true;
    for (int i = 0; i < ((int)numbers.size() / 2); i++) {
        if (numbers[i] != numbers[numbers.size() - 1 - i]) ans = false;
    }
    return ans;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    eratos();
    int N, x;
    cin >> N;
 
    x = N;
    while (1) {
        if (!isPrime[x] && isPalindrome(x)){
            cout << x << '\n';
            break;
        }
        x++;
    }
    return 0;
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1747.cpp

travelbeeee/ProblemSolving

---