오래된 금고 하나가 어느 고대 유적에서 발견되었다. 이 금고는 \(1\) 부터 정수 \(N\) 까지를 자물쇠 눈금으로 가지며, 눈금 중 소수에 해당하는 지점에만 톱니가 박혀 있다.

전설에 따르면, 금고는 \(N\) 이하의 소수들 중 연속한 두 소수 사이의 간격이 가장 큰 구간을 알아야 열린다고 한다. 즉 \(N\) 이하의 소수를 크기 순으로 나열했을 때, 바로 이웃한 두 소수의 차이가 최대가 되는 곳을 찾아야 한다.

\(N\) 이하의 소수를 \(p_1 < p_2 < \cdots < p_k\) 라 하자. 인접한 두 소수의 간격 \(p_{i+1} - p_i\) 중 최댓값과, 그 최대 간격이 시작되는 소수 \(p_i\) (즉 더 작은 쪽 소수) 를 구하여라. 만약 최대 간격을 가지는 구간이 여러 개라면, 시작 소수가 가장 작은 것을 답으로 한다.

\(N\) 이 주어질 때 금고를 여는 두 수를 출력하는 프로그램을 작성하여라.

\(3 \le N \le 2{,}000{,}000\)

\(N\) 이하에 소수가 두 개 이상 존재함이 보장된다.

첫째 줄에 정수 \(N\) (\(3 \le N \le 2{,}000{,}000\)) 이 주어진다.

\(N\) 이하에는 항상 서로 다른 소수가 두 개 이상 존재한다.

한 줄에 두 정수를 공백으로 구분하여 출력한다. 첫 번째 수는 인접한 두 소수 사이 간격의 최댓값이고, 두 번째 수는 그 최대 간격이 시작되는 소수(더 작은 쪽)이다. 최대 간격을 이루는 구간이 여럿이면 시작 소수가 가장 작은 것을 출력한다.

riseoj 작성

출처 Original