[BaekJoon] 1644 소수의 연속합

🔦 문제 링크

✍️ 나의 풀이

---

• 에라토스테네스의 체 + 투 포인터 문제

• 에라토스테네스의 체에서 현재 값의 $i^2$이 N을 넘지 않을 때까지 계산한다.

• 연속합의 모든 경우의 수를 계산하면 $O(n^2)$ 이므로 $(4000000^2)$ 이므로 절대 불가능하다.

• 따라서 투 포인터를 이용해 $O(2n)$으로 계산할 수 있다.

🛠 나의 코드

---

n = int(input())
check = [False] * (n+1)
arr = []

def erato():
    for i in range(2, n+1):
        if not check[i]:
            k = 2
            if i*i > n:
                continue
            while k*i <= n:
                j = k * i
                check[j] = True
                k += 1
    for i in range(2, n + 1):
        if not check[i]:
            arr.append(i)


def sum_function():
    count = 0
    length = len(arr)
    left = right = sm = 0
    while True:
        if sm >= n:
            sm -= arr[left]
            left += 1
        elif sm < n:
            if right == length:
                break
            sm += arr[right]
            right += 1
        if sm == n:
            count += 1

    return count
erato()
print(sum_function())

📝 정리

---

• 투 포인터 사용법

🎈 참고

---