USACO 2006- 킹왕짱소인 > 문제은행 : 정보올림피아드&알고리즘




1172 : 킹왕짱소인

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
7 회   
시도횟수
71 회   

문제

소들은 누가 최고의 소인(소를 식별하는 번호)을 가지고 있는지를 가지고 자주 다툰다. 최근에 가장 최고라고 여겨지는 소인은 ‘킹왕짱소인'라고 불리는 소인이다. 소인 0으로 시작 되지 않는 어떤 임의의 양의 정수로 구분이 된다.

 

'킹왕짱소인'이란 소인인 숫자를 D자리 이상의 두 부분으로 나눴을 때의 숫자가 소수일 경우를 말한다. 가령 D=2 일 경우, 11329는 113과 29로 나눴을 때 ,두개의 숫자가 소수이므로 이는 '킹왕짱소인'이라 할 수 있다.

 

소수의 소들만 '킹왕짱소인'을 가지고 있으나, 대부분의 소들이 이를 가지고자 원한다. 다행히도 소인은 변경이 가능하나, 현재의 소인보다 높은 숫자를 새로 찍는 것만 가능하다. 

 

현재 소의 소인 N(1≤N≤2,000,000,000)과 D가 주어질 경우 N보다 크거나 같은, 새로 얻을 수 있는 '킹왕짱소인'이 어떤 것이 있는지 찾아내는 프로그램을 작성하라. 답이 2,000,000,000을 넘는 경우는 없다고 가정하자.

 


입력형식

입력 파일은 한줄로 이루어지며, 2개의 숫자 D와 N이 공백을 사이에 두고 입력된다.

출력형식

N보다 크거나 같은 '킹왕짱소인' 중 가장 작은 숫자를 출력한다.

입력 예

2 11328

출력 예

11329

입력 예

3 10101

출력 예

101101

출처

USACO 2006

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP