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

 

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

1747번: 소수&팰린드롬

[난이도] Gold5
[유형] 에라토스테네스의 체

[풀이]
N의 최댓값이 100만보다 넉넉하게 큰 수인 500만까지 에라토스테네스의 체를 이용해 어느것이 소수인지
배열에 체크해준다.
그 뒤 N보다 큰 소수중에 가장 작은 팰린드롬인 수를 찾으면 시간내에 해결이 가능하다.

 

#include <cstdio>
#include <string>
using namespace std;
int N;
const int mxN=5e6;
bool np[mxN];
bool check(int n){
    string s = to_string(n);
    int sz = s.size();
    for(int i=0;i<sz/2;i++){
        if(s[i]!=s[sz-1-i]) return 0;
    }
    return 1;
}
int main(){
   scanf("%d",&N);
   np[1]=1;
   for(int i=2;i<mxN;i++){
       if(np[i]) continue;
       for(int j=i+i;j<mxN;j+=i) np[j]=1;
   }
   for(int i=2;i<mxN;i++){
       if(i>=N && !np[i] && check(i)){
           printf("%d",i);
           return 0;
       }
   }
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1747.cpp