[이진 탐색] 백준 1644번: 소수의 연속합 / 골드 3

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

1644번: 소수의 연속합

n = int(input())

a = [False, False] + [True]*(n-1)
primes = []
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

for i in range(1, len(primes)):
    primes[i] += primes[i-1]


def bsearch(left, target):
    right = len(primes)-1
    while left <= right:
        mid = (left + right) // 2
        if primes[mid] < target:
            left = mid + 1
        elif primes[mid] > target:
            right = mid - 1
        else:
            return 1
    return 0

result = 0
result += bsearch(0, n)
for i in range(len(primes)-1):
    result += bsearch(i, n + primes[i])

print(result)

이진 탐색으로 풀어서 이진 탐색으로 분류하였다.

소수를 찾는 과정에서 에라토스테네스의 체를 사용하였다. 

 

# 에라토스테네스의 체
a = [False, False] + [True]*(n-1)
primes = []
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