백준-1261-소수의 연속합

문제

소수의 연속합

풀이

문제조건 해석

어떤 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수 구하는 문제

알고리즘

1. N보다 작은 소수의 배열을 구하기 위해 에라노스테네스의 체 사용

2. 연속된 소수의 합이 N이 되는지를 보기 위해 부분합 사용

   나는 부분합 배열을 구한 뒤 전부 순회하면서 구했으나 $O(N+N^2)$

   문제 의도는 투 포인터를 사용하는 방법으로, 훨씬 빠른 시간에 답을 구할 수 있다. 마이구미의 HelloWorld

코드

n = int(input())

a = [False, False] + [True]*(n-1)

for i in range(2, int(n**(1/2)+1)):
    if a[i]:
        for j in range(i+i, n+1, i):
            a[j] = False
primes = [x for x in range(n+1) if a[x]]

s = [0]
for i in primes:
    s.append(s[-1]+i)

answer = 0
for i in range(len(s)):
    for j in range(i, -1, -1):
        if s[i]-s[j] == n:
            answer += 1
            break
        if s[i]-s[j] > n:
            break

print(answer)

배운점

• 에라토스테네스의 체 코드는 꼭 기억해두자.