💡 문제
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
💭 접근
이 문제는 주어진 자연수 n보다 작거나 같은 소수를 모두 뽑은 뒤, 이들의 연속합이 n이 되는 경우를 세는 문제로, 먼저 에라토스테네스의 체 알고리즘을 사용하여 소수를 생성한다.
이후, 이 문제는 투포인터와 누적합을 사용하여 해결할 수 있는데,
투포인터 알고리즘 같은 경우 부분배열의 시작 인덱스와 끝 인덱스를 조절하며 부분배열의 합이 크거나 같다면 시작 인덱스의 원소를 빼서 합을 줄이고,
부분배열의 합이 작다면 끝 인덱스를 증가시킨 후 다음 원소를 더해 합을 키워주며 앞으로 나아가면 된다.
누적합 알고리즘의 경우 입력으로 주어진 n보다 작거나 같은 소수들의 누적합을 구한 뒤, 2중 for문으로 해결할 수 있다.
📒 코드
# 투 포인터 풀이
def seive_of_erastothenes(n):
if n == 1:
return [0]
is_prime = [1 for _ in range(n + 1)]
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i**2, n + 1, i):
is_prime[j] = 0
return [i for i in range(2, n + 1) if is_prime[i]]
n = int(input())
prime = seive_of_erastothenes(n)
ans = 0
left = 0
right = 0
tmp = prime[0]
while left <= right:
if tmp >= n:
if tmp == n:
ans += 1
tmp -= prime[left]
left += 1
else:
right += 1
if right >= len(prime):
break
tmp += prime[right]
print(ans)# 누적합 풀이
def seive_of_erastothenes(n):
if n == 1:
return [0]
is_prime = [1 for _ in range(n + 1)]
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i**2, n + 1, i):
is_prime[j] = 0
return [i for i in range(2, n + 1) if is_prime[i]]
n = int(input())
prime = seive_of_erastothenes(n)
p_sum = prime[:]
for i in range(1, len(p_sum)):
p_sum[i] += p_sum[i - 1]
ans = 0
start = 0
for i in range(len(p_sum)):
if p_sum[i] == n:
ans += 1
continue
for j in range(start, i):
if p_sum[i] - p_sum[j] == n:
ans += 1
elif p_sum[i] - p_sum[j] > n:
continue
elif p_sum[i] - p_sum[j] < n:
start = j
break
print(ans)💭 후기
기본적인 투포인터 알고리즘과 누적합 알고리즘을 사용하는 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/1644
