원더프라임 브랜드

시간 제한1초메모리 제한128 MB

요약
D와 N이 주어질 때, 자릿수를 두 부분으로 나눴을 때 각 부분이 길이 D 이상의 소수이고 0으로 시작하지 않는, N 이상인 가장 작은 정수를 구한다.
난이도

보통10점 중 7점

유형
정수론, 완전 탐색, 수학, 구현
정답자
아직 제출이 없습니다

문제

소들은 누구의 브랜드가 가장 멋진지 늘 겨룬다. 요즘 가장 인기 있는 것은 "원더프라임(wonderprime)" 브랜드다. 브랜드는 00으로 시작하지 않는 숫자들의 나열이며, 사실상 양의 정수처럼 보인다.

원더프라임이란, 그 숫자열을 앞부분과 뒷부분 두 조각으로 나눌 수 있어(두 조각을 이어 붙이면 원래 수가 된다), 각 조각이 모두 소수이고, 각 조각이 적어도 DD자리 이상이며, 어느 조각도 00으로 시작하지 않는 수를 말한다.

예를 들어 D=2D=2일 때 1132911329는 원더프라임이다. 113113과 2929로 나눌 수 있고, 둘 다 소수이기 때문이다.

정수 NN이 주어질 때, NN 이상인 가장 작은 원더프라임을 구하여라. 1≤N≤2,000,000,0001 \le N \le 2{,}000{,}000{,}000이며, 정답이 2,000,000,0002{,}000{,}000{,}000을 넘는 경우는 없음이 보장된다.

입력

첫째 줄에 두 정수 DD와 NN이 공백으로 구분되어 주어진다.

출력

첫째 줄에 NN 이상인 가장 작은 원더프라임을 출력한다.

예제4

  1. 예제 1

    입력
    2 11328
    
    예상 출력
    11329
    
  2. 예제 2

    입력
    2 11329
    
    예상 출력
    11329
    
  3. 예제 3

    입력
    1 10
    
    예상 출력
    22
    
  4. 예제 4

    입력
    2 1000
    
    예상 출력
    1111