[백준1644] 소수의 연속합

문제

---

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

1644번: 소수의 연속합

 

생각의 흐름

---

 

에라토스테네스의 체를 이용하여 prime 리스트를 채워준뒤 brute-force를 이용하여 풀면 된다.(이 부분은 코드로 확인하는 편이 이해가 더 빠르다.)

 

코드

---

# BOJ 1644

n = int(input())
prime = [1]*(n+1)
for i in range(2, n+1):
    if prime[i]:
        t=2
        while i*t<=n:
            prime[i*t]=0
            t+=1
ans = 0
for i in range(n, 1, -1):
    if prime[i]:
        tmp = 0
        for j in range(i, 1, -1):
            if prime[j]:
                tmp+=j
                if tmp==n:
                    ans+=1
                    break
                elif tmp>n:
                    break
print(ans)