백준 28427

다음 쿼리를 수행하는 프로그램을 작성하시오.

$L\ R$: $L \leq x < y \leq R$을 만족하는 정수 $x$, $y$에 대하여,
$x \leq k \leq y$를 만족하는 모든 자연수 $k$의 합이 소수가 되게 하는 모든 정수 쌍 $(x, \:y)$의 개수를 출력한다.
첫째 줄에 쿼리의 개수 $Q$가 주어진다.
$(1 \leq Q \leq 500\ 000)$ 
다음 $Q$개의 줄에는 각각의 쿼리를 나타내는 양의 정수 $L$, $R$이 주어진다.
$(2 \leq L < R \leq 500 \ 000)$ 

풀이

문제를 보고 바로 떠오른 개념은 누적합, DP였다.
쿼리(test case)의 개수, L, R이 5*10^5이기 때문에 쿼리 내부의 연산은 선형/로그시간이여야 한다. 그렇기 때문에 DP table을 만들어 누적합 개념으로 접근한다는 생각을 가지고 이 문제를 풀기 시작했다.

처음에는 모든 구간을 저장하는 테이블을 만든다는 생각을 했다. 하지만 그러면 5*10^5 * 5*10^5의 이중배열이 필요하기 때문에 단순 일차원 누적합 배열로 문제를 풀어야겠다는 생각을 했다. 하지만 k의 합이 소수가 되게하는 규칙에서 많은 고민을 하게 되었다.

k의 값들은 항상 연속한다. 그리고 두개 이상의 원소가 연속할 경우, 그것을 더한 값이 소수인 경우를 찾는 것이다. 그러면 초항을 a라 하고, 이것이 i = 1 부터 어떤 특정한 수 n까지 가게되기 때문에 식으로 정리하면 $\sum_{i=1}^{n}a+i$가 된다.
그리고 이 식을 정리하면 $na + n(n+1)/2$가 된다.
이를 다시 정리하면 $n(a + (n+1)/2)$가 되는데. 여기서 우리가 증명하고자 하는 것은 "연속하는 정수 n개의 합이 소수이다." 라는 것 이다.
하지만 n이 2일 경우를 제외하면, 항상 이 식은 n, 또는 n/2라는 약수를 가지게 된다. 그러므로 귀류법으로 결론을 내리면 연속하는 두개의 정수를 더하는 경우 되의 n > 2인 경우에는 연속하는 n개의 정수를 더하면 소수가 될 수 없다. 라는 것을 증명할 수 있다.
그러므로 연속하는 두개의 정수가 소수일 경우를 판별해주고, 이 값들을 누적합을 통해 테이블에 갱신하고, 계산하면 된다.