BOJ 6210 Wonderprime Brands

원하는 수의 왼쪽 길이를 $l$로, 오른쪽 길이를 $r$로 고정하고, $N$의 오른쪽 $r$자리를 끊어서 그 값을 $N_r$, 왼쪽의 나머지 부분의 값을 $N_l$이라고 합시다. 그러면 다음과 같은 문제가 됩니다.

• 최소의 $P_l \times 10^r + P_r$을 구합니다. 이 수는 $N_l \times 10^r + N_r$ 이상이면서, $P_l \ge 10^{l-1}$, $P_r \ge 10^{r-1}$ (0으로 시작하지 않음)이고, $P_l$과 $P_r$은 각각 소수여야 합니다.

먼저, $N_l$이 $10^{l-1}$ 이상의 소수인지 확인합니다. 그렇다면 $N_r$ 이상이면서 $10^{r-1}$ 이상인 가장 작은 소수를 확인합니다. 이 소수 $p$가 $10^r$ 미만이라면, $P_l = N_l, P_r = p$가 답이 됩니다.

$N_l$이 조건을 충족하지 못했거나 $p > 10^r$이면, $N_l$을 초과하는 $10^{l-1}$ 이상의 가장 작은 소수 $q_1$을 찾습니다. 그러면 $P_r$은 $10^{r-1}$ 이상의 가장 작은 소수 $q_2$로 두면 $P_l = q_1, P_r = q_2$가 답이 됩니다.

$x$ 이상의 가장 작은 소수 찾기는 $\mathcal{O}(\sqrt{x})$ 시간의 소수 판별을 이용하여 나이브하게 구현해도 충분히 빠르게 계산할 수 있습니다. 이는 소수들 사이의 최대 간격이 크지 않음을 이용합니다.