백준 1747 소수&팰린드롬

<링크>

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

<소스코드>

#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int p[2000001];
vector<int> v;
void sieve();
int isPal(int);
int main()
{
    sieve();
    for (int i = 2; i <= 2000000; ++i)
        if (!p[i] && isPal(i))
            v.push_back(i);
    int N;
    scanf("%d", &N);
    printf("%d", *lower_bound(v.begin(), v.end(), N));
}
int isPal(int n)
{
    string s = to_string(n);
    int i = 0;
    int j = s.length() - 1;
    while (i <= j)
    {
        if (s[i] != s[j])
            return 0;
        ++i;
        --j;
    }
    return 1;
 
}
void sieve()
{
    int s = sqrt(2000000);
    for (int i = 2; i <= s; ++i)
    {    
        if(!p[i])
        for (int j = i * 2; j <= 2000000; j += i)
        {
            p[j] = 1;
        }
    }
}

<풀이>

소수하면 걍 떠오르는게 에라토스테네스의 체라서 일단 그렇게 구현하려했는데,

100만보다 크면서 팰린드롬인 소수는 어디까지 가야 있을지를 모르겠었다.

즉 , 배열을 얼마만큼 잡아야할지 각이 안나왔다.

그래서 대충 200만까지 잡고 돌려봤다.

1003001이 출력될 수 있는 가장 큰 값이었다.

체를 이용해서 소수인 애들을 체크해놓고

팰린드롬인애들만 벡터에 집어넣었다.

팰린드롬인지 체크하는 시간은 (2~1003001 사이의 소수의 개수)*숫자의 길이이다.

수의 길이는 최대 7이므로 시간 내에 들어온다.

그래서 팰린드롬은 그냥 노가다로 체크했다.

N이상이면서 가장 작은 수를 출력해야 하기 때문에

lower_bound를 이용했다.