[백준/Python] 1644번 소수의 연속합

문제

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

풀이

def primef():
    limit = 4000000  
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    return [i for i in range(limit + 1) if is_prime[i]]

n = int(input())

primelist = primef()
answer = 0
start, end, data = 0, 0, 0  

while start < len(primelist):  
    if data == n:
        answer += 1
        data -= primelist[start] 
        start += 1
    elif data < n:
        if end < len(primelist):  
            data += primelist[end]
            end += 1
        else:
            break  
    else:
        data -= primelist[start]
        start += 1

print(answer)

 

에라토스테네스의 체와 투포인터를 이용한 연속합 풀이입니다. 

 

에라토스테네스의 체를 이용하여 소수 리스트를 만들고 시작점과 끝점을 0, 0부터 시작해서 전체 탐색을 합니다.