[Python] BOJ 1644번. 소수의 연속합

작성일 | In |

1644번. 소수의 연속합

문제 링크

풀이 코드

  • 에라토스테네스의 체와 두포인터를 사용하는 문제입니다.
  • 먼저 체를 통해서 소수들만 골라줍니다.
  • 두포인터를 사용하여 현재 합이 n보다 작으면 오른쪽으로 늘려주고, 크면 왼쪽을 빼줍니다.
  • 같을 경우는 오른쪽을 늘려줍니다.
  • 아래 코드에서는 pList의 범위를 n+1로 잡았지만, 마음 편하게 4000000+1로 잡고 아래 int(math.sqrt(n) + 1도 3000정도로 잡는 것이 편합니다. (실제로 제출은 이렇게 했습니다!)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 1644번. 소수의 연속합


import math, sys

n = int(input())
if n == 1:
    print(0)
    sys.exit()
# 소수 리스트 만들어주기 (에라토스테네스의 체)
pList = [True for i in range(n + 1)]
pList[1] = False
for i in range(2, int(math.sqrt(n) + 1)):
    if pList[i]:
        for j in range(i + i, n + 1, i):
            pList[j] = False

onlyPrimes = []
for i in range(2, n + 1):
    if pList[i]:
        onlyPrimes.append(i)

ans = 0
l = 0
r = 0
cur = onlyPrimes[0]
while True:
    if l > r:
        break
    if cur > n:
        cur -= onlyPrimes[l]
        l += 1
    elif cur < n:
        r += 1
        if r == len(onlyPrimes):
            break
        cur += onlyPrimes[r]
    else:
        ans += 1
        r += 1
        if r == len(onlyPrimes):
            break
        cur += onlyPrimes[r]
print(ans)

비고