1644. 소수의 연속합

문제

백준 1644번 소수의 연속합

---

풀이

보자마자 투포인터 쓰는 문제인 것도 알았는데.. 계속 시간초과 떠서 멘붕이었다.
아니 제곱근으로 범위도 줄였는데 대체 뭐가 문제야??? 라고 수천번 생각하다가 에라토스테네스로 푸니까 느릿느릿 채점된다..

나는 어떤 경우에든 2~제곱근까지 훑는 방법이 가장 빠른 줄 알았는데 잘못 알고있었다.

• 에라토스테네스의 체

  특정 범위 내의 모든 소수를 찾는 경우 가장 효율적.
  즉 대량의 소수를 판별할 경우 가장 빠른 속도를 보인다.
  시간복잡도는 O(NlogN)

• 2~제곱근까지 약수를 통한 판별

  특정 숫자 N에 대한 소수 판별시 유용.
  (이 경우 에라토스테네스의 체를 활용하면 필요없는 숫자까지 판별하기 때문에 N이 커질수록 비효율적)
  시간복잡도는 O(N^1/2)

그렇다고한다..

그렇게 장장 6번의 시도 끝에 맞았습니다!! 떴다.

from math import sqrt

n = int(input())
num = [1] * (n+1)
for i in range(2, n+1):
    for j in range(i, n//i+1):
        num[i*j] = 0
prime = [i for i in range(2, n+1) if num[i]]

cnt = 0
l, r = 0, 1
while l <= r and l <= len(prime) and r <= len(prime):
    s = sum(prime[l:r])
    if s >= n: 
        if s == n: cnt += 1
        l += 1
    else: r += 1
print(cnt)

---

부족한 점

투포인터에서 인덱스에러 주의할 것