[BOJ / Python] 1644 - 소수의 연속합

문제 링크

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

---

풀이

• 에라토스테네스의 체를 사용해 n 보다 작거나 같은 소수들을 구합니다. (line 2~ line 8)
  • 소수를 담을 배열 prime을 선언합니다.
  • 배열 a는 소수가 아닌 수를 지우기 위해 사용됩니다.
  • 2 ~ n 범위의 수 중에서 소수를 채택하고, 그 소수의 배수는 모두 지우게 됩니다. 
• 투 포인터를 이용해 연속된 수열(소수)의 부분합을 구합니다. (line 9 ~ line 19) 
  • left, right의 초기 인덱스를 0,0으로 설정합니다.
  • 우측 포인터를 가리키는 right의 인덱스가 소수를 담은 배열 prime의 길이보다 크다면 반복문을 종료하게 됩니다.
  • left~right 사이의 소수 합을 구해 cal에 담습니다.
  • cal이 n이라면 문제에서 원하는 경우의 수이므로 cnt를 1 올려주고 left 포인터의 인덱스를 우측으로 이동시킵니다.
  • cal이 n보다 크다면 left 포인터의 인덱스를 우측으로 이동시킵니다.
  • cal이 n보다 작다면 right 포인터의 인덱스를 우측으로 이동시킵니다. 

---

코드

n = int(input())
prime = []
a = [0,0]+[1]*(n-1)
for i in range(2, n+1):
    if a[i]:
        prime.append(i)
        for j in range(2*i, n+1, i):
            a[j] = 0
left, right = 0, 0
cnt = 0
while(right < len(prime)):
    cal = sum(prime[left:right+1])
    if cal == n:
        cnt+=1
        left +=1
    elif cal > n:
        left+=1
    else:
        right+=1
print(cnt)