백준 28427 Tricknology (Python,Pypy)

문제는 이하와 같습니다.

import sys

input = sys.stdin.readline
N = int(input())
A = []
maximum = []
for i in range (0,N):
    a = list(map(int,input().split()))
    A.append(a)
    b = max(a)
    maximum.append(b)

M = max(maximum)
prime_cnt = [0] * (2*M +1)
num = [0] * (2*M + 1)
num[0] = 1
num[1] = 1
for i in range (2,2*M+1):
    if num[i] == 0:
        prime_cnt[i] = prime_cnt[i-1] + 1
        for j in range (2*i,2*M+1,i):
            num[j] = 1
    else:
        prime_cnt[i] = prime_cnt[i-1]

#Hint: 3개 이상의 연속한 정수의 합은 소수가 될 수 없다.
for i in range (0,N):
    cnt = prime_cnt[2*A[i][1]-1] - prime_cnt[2*A[i][0]]
    print(cnt)

해당 코드의 Hint:

3개 이상의 연속한 자연수를 합한 결과는, 반드시 합성수가 된다는 것에 기인합니다.

n(>2)개의 연속한 자연수를 써보면

k, k+1, k+2, ... , k +(n-1)로 주어지고, 이들의 합은 kn + (n(n-1)/2) 꼴로 나타낼 수 있습니다.

자연스럽게 n을 공통 인수로 갖고있고, n(k + (n-1)/2) 로 나타낼 수 있습니다.

만약 n이 홀수라면 (n-1)/2의 부분은 자연스럽게 정수가 되고, n의 배수, 즉 합성수가 되겠습니다.

한편 n이 짝수라면 n = 2m으로 쓸 수 있으므로
2m(k + (2m-1)/2) = m(2k + 2m - 1) 로 쓸 수 있겠습니다.
각각의 m과 2k + 2m -1 은 정수입니다.

여기서 n이 3이상이라고 하였으므로, m은 2 이상의 자연수가 될 것이고, m(2k + 2m -1)은 m의 배수가 되면서, 결국 합성수가 되겠습니다.

즉 가능한 것은 연속한 두 수의 합으로 나타낼 수 있는 소수 이며,
이것들의 counting을 얼마나 빠르게 구현할 수 있는가가 이 문제의 해결방법이 되겠습니다.