[알고리즘] 백준 1644 소수의 연속합 / pyhton

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

1644번: 소수의 연속합

 

검색해서 에라토스테네스의 체 코드를 이용해 N이하의 소수배열을 구하고(여기를 참고)

2003번문제와 동일한 방법으로 연속된 합을 구했다.

 

def isPrime(n):
    a = [False,False] + [True]*(n-1)
    for i in range(2,n+1):
        if a[i]:
            primes.append(i)
            for j in range(2*i, n+1, i):
                a[j] = False
                
primes = []
N = int(input())
isPrime(N)
left, right, result = 0, 0, 0
if len(primes) == 0:
    hap = 0
else:
    hap = primes[0]

while left <= right and right < len(primes):
    if hap <= N:
        if hap == N:
            result += 1
        right += 1
        if right < len(primes):
            hap += primes[right]
    elif hap > N:
        hap -= primes[left]
        left += 1
print(result)