[백준] 1644 소수의 연속합 (python 파이썬)

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

1644번: 소수의 연속합

---

저번에 푼 부분합 문제의 소수 버전.

비슷한 문제여서 금방 해결 가능했다.

---

아이디어

1. 소수 찾기

• 시간 복잡도가 빠른 에라토스테네스의 체 방법으로 소수를 찾았다.

2. 소수의 연속합

• 부분합 문제와 유사하게 투 포인터를 사용해서 경우의 수를 찾았다.

 

---

전체 코드

import math
n = int(input())

if n == 1:
    print(0)
    exit(0)

arr = [True] * (n + 1)
arr[0] = False
arr[1] = False

for i in range(2, int(math.sqrt(n)+1)):
    if arr[i] == True:
        j = 2

        while (i * j) <= n:
            arr[i*j] = False
            j += 1

prime_list = []
for i in range(2, n + 1):
    if arr[i] == True:
        prime_list.append(i)

left = 0
right = 0
temp_prime_sum = prime_list[0]
count = 0

while left <= right:

    if temp_prime_sum > n:
        temp_prime_sum -= prime_list[left]
        left += 1
    else:
        if temp_prime_sum == n:
            count += 1
        right += 1
        if right == len(prime_list):
            break
        temp_prime_sum += prime_list[right]

print(count)

---

코드 설명

import math
n = int(input())

if n == 1:
    print(0)
    exit(0)

arr = [True] * (n + 1)
arr[0] = False
arr[1] = False

for i in range(2, int(math.sqrt(n)+1)):
    if arr[i] == True:
        j = 2

        while (i * j) <= n:
            arr[i*j] = False
            j += 1

prime_list = []
for i in range(2, n + 1):
    if arr[i] == True:
        prime_list.append(i)

먼저 에라토스테네스의 체 방법으로 N까지 소수를 찾아준다.

이후 소수들을 prime_list에 넣어준다.

 

여기서 N이 1인 경우 아래의 코드에서 index에러가 나므로

N이 1일 때는 0을 출력하고 종료시켜준다.

 

left = 0
right = 0
temp_prime_sum = prime_list[0]
count = 0

while left <= right:

    if temp_prime_sum > n:
        temp_prime_sum -= prime_list[left]
        left += 1
    else:
        if temp_prime_sum == n:
            count += 1
        right += 1
        if right == len(prime_list):
            break
        temp_prime_sum += prime_list[right]

print(count)

temp_prime_sum이라는 소수의 합을 저장해 줄 변수를 선언한다.

이 값이 우리가 구하는 n보다 크면

left를 한 칸 옮겨서 temp_prime_sum값에 가장 왼쪽에 있는 소수(prime_list[left])를 빼준다.

n보다 작으면 right를 한칸 옮겨서 prime_list[left]를 더해준다.

n과 같으면 count에 1 더 해주면 된다.