백준 1644번: 소수의 연속합 (Python)

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

---

 

풀이

1) 주어진 N에 대하여, N 이하의 소수를 모두 포함하는 리스트를 만든다.

2) 투 포인터 left, right = 0에서 시작하여, left부터 right까지의 부분합을 계산한다. 부분합이 N보다 크면 left를 1 늘려 왼쪽 범위를 줄여주며, N보다 작으면 right를 1 늘려 오른쪽 범위를 늘려준다. 만약 같으면 count를 1 늘려주고, right, left 둘다 1 늘려준다.

 

유의점

1) right쪽에서 out of range가 안 뜨도록 조절해주자. 적당히 요령껏.

2) 소수를 쌩으로 구하면 시간초과가 뜨니, 에라토스테네스의 체 알고리즘으로 구해준다

 

내 실수

1) 소수를 2e06 범위까지 고정적으로 구해주었다(코드를 처음 구현할 때, 4000000은 2000000 2개보다 작으니까와 같은 안일한 생각을 했다.). But 200만보다 큰 소수(예시: 3999971)는 자기 자신만의 합도 연속합이기에 이 경우를 무시하게 된다. 그래서 4e06까지 소수를 구해주었다.

 

초기 코드

N = int(input())
count = 0

prime_list = [False, False] + [True] * int(4e06 + 10000)
for i in range(len(prime_list)):
    if prime_list[i]:
        for j in range(2*i, len(prime_list), i):
            prime_list[j] = False
prime_list = [i for i in range(len(prime_list)) if prime_list[i]]

left = right = 0
temp = 2
while prime_list[left] <= N:
    if temp < N:
        right += 1
        if right >= len(prime_list):
            break
        temp += prime_list[right]
    elif temp > N:
        temp -= prime_list[left]
        left += 1
    else:
        count += 1
        temp -= prime_list[left]
        right += 1
        left += 1
        temp += prime_list[right]

print(count)

 

개선점)

1) Given N보다 작거나 같은 소수만 찾으면 되는데? -> prime_list 범위를 줄여준다.

2) 소수 찾을 때, sqrt(N)보다 작거나 같은 범위에서만 확인해도 되는데? -> 1)에 비해 그렇게 크리티컬한 요소는 아니라고 생각하지만, O(nloglogn) 알고리즘에서 O(n) 정도를 줄일 수 있는 방법이다. n이 그렇게 크지는 않으므로(<= 4e06), 의미있지 않을까 싶다.

 

 

개선된 코드

N = int(input())
count = 0

prime_list = [False, False] + [True] * N
for i in range(int(len(prime_list)**0.5) + 2):
    if prime_list[i]:
        for j in range(2*i, len(prime_list), i):
            prime_list[j] = False
prime_list = [i for i in range(len(prime_list)) if prime_list[i]]



left = right = 0
temp = 2
while prime_list[left] <= N:
    if temp < N:
        right += 1
        if right >= len(prime_list):
            break
        temp += prime_list[right]
    elif temp > N:
        temp -= prime_list[left]
        left += 1
    else:
        count += 1
        temp -= prime_list[left]
        right += 1
        left += 1
        if right >= len(prime_list):
            break
        temp += prime_list[right]

print(count)

개선되었다.