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

시간 제한	메모리 제한
2 초	128 MB

 

문제 (링크)

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

1644번: 소수의 연속합

 

나의 풀이

import sys
import math

n = int(sys.stdin.readline())

# n이하의 수 중 소수를 찾아줄 배열 (에라토스테네스의 체)
prime_checker = [True for _ in range(n+1)]

# 소수가 아닌 0과 1에 대해 별도의 False처리
prime_checker[0:2] = False

for i in range(2, int(math.sqrt(n)) + 1):
	if prime_checker[i]:
    	j = 2
        while i * j <= n:
        	arr[i *j] = False
            j += 1

# n이하의 소수값을 담아줄 배열
arr = []
for i in range(n+1):
	if prime_checker[i]:
    	arr.append(i)

# arr에 대해서 투 포인터 알고리즘
end = 0
intervalSum = arr[0]
cnt = 0 # 경우의 수를 담아줄 변수

for start in range(len(arr)):
	while intervalSum < n and end < len(arr):
    	end += 1
        if end == len(arr):
        	break
        intervalSum += arr[end]
        
	if intervalSum == n:
    	cnt += 1
	
    intervalSum -= arr[start]

print(cnt)

 

접근 방법 및 코드 설명

기존의 투 포인터 알고리즘(배열의 연속된 값)에 소수 값들에 대한 처리를 해줘야하는 에라토스테네스의 체 방식을 결합시켜야하는 방식이다. 

 

입력 받은 n값에 대하여 2 ~ n까지의 모든 소수를 찾기 위해서 에라토스테네스의 체 방식을 사용해 걸러주고, 해당 소수를 arr라는 새로운 배열에 담아준다.

 

 arr에 2 ~ n까지의 소수값들이 담기고 나면, 기존의 투 포인터 방식을 이용해 intervalSum값을 구해주고 해당 값이 입력값 n과 같다면 경우의 수를 세 주는 cnt 변수에 1을 더해주는 방식이다.

 

두 개의 알고리즘을 모두 알고 있다면 어렵지 않게 짤 수 있는 코드였다.

 

 

투 포인터 알고리즘 - seongonion.tistory.com/47?category=868991

소수 판별 알고리즘 - seongonion.tistory.com/43?category=868991