3개 이상의 연속된 자연수의 합은 반드시 소수가 아니다

1. 연속된 자연수의 합

 

2개의 연속된 자연수를 합해보면..

 

1+2 = 3

 

2+3 = 5

 

3+4 = 7

 

4+5 = 9

 

... 소수가 나올 수 있는데

 

3개 이상의 연속된 자연수를 합해보면..

 

1+2+3 = 6

 

2+3+4 = 9

 

3+4+5 = 12

 

4+5+6 = 15

 

... 일단 소수가 보이질 않는다.. 이게 우연일까?

 

자연수 x에 대하여 n개의 연속된 자연수의 합은 다음과 같이 나타난다.

 

$$S = x + (x+1) + (x+2) + ... + (x+n-1) = nx + \frac{(n-1)n}{2}$$

 

여기서 n이 3이상의 자연수일때, S가 반드시 합성수임을 보이고자 한다.

 

1) 만약 n이 짝수라면 $n = 2k$ 여기서 k는 2이상의 자연수이다. 

 

$$S = 2kx + k(2k-1) = k(2x + 2k - 1)$$

 

여기서 k는 2이상의 자연수이고, x는 1이상의 자연수이므로, 2x+2k-1이 5이상의 자연수이다.

 

그러므로 S는 소수가 아니다. 

 

2) 이번엔 n이 홀수라고 한다면.. $n = 2k+1$이고, k는 1이상의 자연수이다. 그렇다면..

 

$$S = (2k+1)x + k(2k+1) = (2k+1)(x+k)$$

 

그런데, k는 1이상의 자연수이고, x가 1이상의 자연수이므로 2k+1은 3이상의 자연수이고 x+k는 2이상의 자연수이다.

 

따라서 S는 소수가 아니다.

 

그러므로, 3개 이상의 연속된 자연수의 합은 반드시 합성수이다.

 

 

2. 문제

 

28427번: Tricknology (acmicpc.net)

28427번: Tricknology

 

 

3. 풀이

 

50만개의 쿼리가 주어지는데, 각 쿼리가 [L,R]로 주어지고, 이 구간에서 잡을 수 있는 모든 정수쌍 (x,y)에 대하여 

 

[x,y]의 자연수 합이 소수가 되는 (x,y)를 구하는 문제

 

단순하게 생각하면 [L,R]이 최악으로 [2,500000]으로 주어지면 모든 정수쌍 (x,y)를 조사하는데만해도... 시간안에 해결 못할듯

 

또한 x = 2, y = 500000이라고 한다면.. [x,y]의 모든 합이 1000억이 넘는데 1000억 내의 소수를 모두 찾는데 1초 넘겠다

 

하지만 3개 이상의 연속된 자연수의 합은 소수가 될 수 없다는 사실을 이해하고 나면..

 

나올 수 있는 최대 소수는 499999 + 500000 = 999999로 100만 이내의 소수들을 에라토스테네스의 체로 찾는다

 

from sys import stdin

def get_prime(n):

    result = [1]*(n+1)

    result[1] = 0

    for i in range(2,int((n+1)**(1/2))+1):

        if result[i] == 1:

            for j in range(i*i,n+1,i):

                result[j] = 0

    return result

prime_list = get_prime(1000000)

 

그런다고 하더라도, [L,R]이 주어지면 O(1)에 정답을 찾지 못하면  1초 안에 문제를 해결하기 쉽지 않다.

 

어떤 구간 [L,R]이 주어진다고 한다면.. 검사해야할 수는..

 

[L,L+1], [L+1,L+2], ... ,[R-1,R]들의 합을 구해보고, 이들이 각각 소수인지 판단한다.

 

그러면 그 소수 여부를 2~50만 인덱스에 대응시켜둔다.

 

 

소수 여부를 담은 리스트는 O(50만)안에 가능할 것

 

그런데 [L,R]이 주어졌을때, O(1)에 구할려면, [L,R]에 들어간 모든 소수의 개수 합을 미리 저장해놓아야한다.

 

그것으로 가능한 자료구조가 누적합

 

각 소수 여부가 인덱스 L,L+1,L+2,...,R-1에 대응되어 있기 때문에.. 누적합을 구해놓는다면..

 

prefix = [0,0]

for i in range(2,500000):
    
    x = i + i + 1

    if prime_list[x] == 1:
        
        prefix.append(prefix[-1] + 1)
    
    else:
        
        prefix.append(prefix[-1])

 

 

[L,R]에서 찾을 수 있는 모든 구간합이 소수가 되는 구간 개수는... prefix[R-1] - prefix[L-1]

 

q = int(stdin.readline())

for _ in range(q):

    l,r = map(int,stdin.readline().split())

    print(prefix[r-1] - prefix[l-1])