문제
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 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 = int(input())
nums = [False, False] + [True]*(N-1)
primes = []
for i in range(2, int(N**0.5) + 1):
if nums[i]:
j = 2
while i*j <= N:
nums[i*j] = False
j += 1
for i in range(N+1):
if nums[i]:
primes.append(i)
cnt = 0
left, right = 0, 0
sum = primes[0]
length = len(primes)
while right < length:
if sum == N:
cnt += 1
left += 1
right += 1
if right < length:
sum = sum - primes[left-1] + primes[right]
elif sum > N:
left += 1
sum -= primes[left-1]
elif right == length-1:
break
else:
right += 1
sum += primes[right]
print(cnt)- 에라토스테네스의 체로
N이하의 소수를 판별해서 리스트에 담는다. 0, 0에서부터 두 포인터를 시작해서 연속된 소수의 합이N이 되는 경우의 수를 구한다.right == N+1이 되는 경우에 while문을 종료할 수 있는 방법을 찾는 것이 어려웠다.
- 97%에서 런타임 에러가 발생했다.
나의 풀이2
N = int(input())
nums = [False, False] + [True]*(N-1)
primes = []
for i in range(2, int(N**0.5) + 1):
if nums[i]:
j = 2
while i*j <= N:
nums[i*j] = False
j += 1
for i in range(N+1):
if nums[i]:
primes.append(i)
cnt = 0
left, right = 0, 0
sum = primes[0]
while right < len(primes):
if sum == N:
cnt += 1
if sum >= N:
left += 1
sum -= primes[left-1]
elif right == len(primes)-1:
break
else:
right += 1
sum += primes[right]
print(cnt)right == N+1이 되는 경우에 반복문 종료 조건이 문제인가 싶어서sum == N인 경우에left와right를 한 칸씩 이동하던 부분을 별개의 if문에서 실행하도록 수정했다.- 하지만 이 풀이도 여전히 97%에서 런타임 에러가 발생했다.
나의 풀이3 (통과)
N = int(input())
nums = [False, False] + [True]*(N-1)
primes = []
for i in range(2, int(N**0.5) + 1):
if nums[i]:
j = 2
while i*j <= N:
nums[i*j] = False
j += 1
for i in range(N+1):
if nums[i]:
primes.append(i)
cnt = 0
left, right = 0, 0
sum = 2
while right < len(primes):
if sum == N:
cnt += 1
if sum >= N:
left += 1
sum -= primes[left-1]
elif right == len(primes)-1:
break
else:
right += 1
sum += primes[right]
print(cnt)- 찾아보니
N = 1인 경우에는 소수가 존재하지 않는데sum = primes[0]에 접근하면서 발생하는 에러였다. N이하의 소수가 존재하는 경우에 최소값은 무조건2가 되기 때문에sum = 2로 초기값을 수정했다.sum초기값만 수정하면 풀이 1번과 2번 모두 문제를 통과할 수 있다.
- 실행 속도는 첫 번째 풀이가 좀 더 빠르다. (가독성 면에서는 두 번째 풀이가 더 좋은 거 같다.)
나의 풀이4 (통과)
N = int(input())
nums = [False, False] + [True]*(N-1)
primes = []
for i in range(2, int(N**0.5) + 1):
if nums[i]:
j = 2
while i*j <= N:
nums[i*j] = False
j += 1
for i in range(N+1):
if nums[i]:
primes.append(i)
cnt = 0
left, right = 0, 0
while right < len(primes):
partial_sum = sum(primes[left:right+1])
if partial_sum == N:
cnt += 1
left += 1
right += 1
elif partial_sum > N:
left += 1
else:
right += 1
print(cnt)sum()을 이용해서 부분합을 구하는 방법도 사용해 봤는데 생각보다 실행 시간이 별로 차이가 안 난다.
