BOJ 1644 · 소수의 연속합

알고리즘 분류 : 투 포인터, 수학  

에라토스테네스의 체로 소수를 먼저 구하고, 구한 소수를 바탕으로 투 포인터 알고리즘을 사용하여 해결할 수 있다.

에라토스테네스의 체는 BOJ 1929번 '소수 구하기'를, 투 포인터는 BOJ 2003번 '수들의 합 2'를 참조.

---

C++ 소스코드

#include <cstdio>
#include <vector>
using namespace std;

int n, sum, ans, left, right;
vector<int> a;

void prime() {
    vector<bool> c(n+1);
    for (int i=2; i*i<=n; i++) {
        if (!c[i]) {
            for (int j=i*i; j<=n; j+=i) {
                c[j] = true;
            }
        }
    }
    for (int i=2; i<=n; i++) {
        if (!c[i]) a.push_back(i);
    }
}

void solve() {
    int k = a.size();
    while (true) {
        if (sum >= n) {
            sum -= a[left];
            left++;
        } else {
            if (right == k) break;
            sum += a[right];
            right++;
        }
        if (sum == n) ans++;
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &n);
    prime();
    solve();
    return 0;
}

---

Python 3 소스코드

n = int(input())
a = []

def prime():
    c = [False]*(n+1)
    for i in range(2, n+1):
        if i*i > n:
            break
        if not c[i]:
            for j in range(i*i, n+1, i):
                c[j] = True
    for i in range(2, n+1):
        if not c[i]:
            a.append(i)

def solve():
    left = right = ans = s = 0
    k = len(a)
    while True:
        if s >= n:
            s -= a[left]
            left += 1
        else:
            if right == k:
                break
            s += a[right]
            right += 1
        if s == n:
            ans += 1
    print(ans)

prime()
solve()

---

참고

• 백준 온라인 저지 : BOJ 1644
• 소수 구하기
• 수들의 합 2