[파이썬] 백준 1644 : 소수의 연속합 (골드3)

[파이썬] 백준 1644 : 소수의 연속합 (골드3)

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

---

풀이

방향성 생각

• N=4백만이라, 에라스토테네스로 소수 리스트 한 번 빠르게 만든 다음 투포인터 사용

• 연속된 소수의 합으로 다른 자연수를 만드는거라 투포인터임을 바로 알 수 있다.

---

전체코드

def prime(n):
    is_prime = [True]*(n+1)
    is_prime[:2] = [False]*2

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

    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

N = int(input())
arr = prime(N)
answer = 0

temp = 0
l,r = 0,0
while r < len(arr):
    if temp < N:
        temp += arr[r]
        r += 1
    elif temp > N:
        temp -= arr[l]
        l += 1
    else:
        answer += 1
        temp -= arr[l]
        l += 1

print(answer + (N in arr))

코멘트

• 자기 자신이 소수인 경우도 포함!