[C++, Python] 투 포인터 2) BOJ 1644 소수의 연속합

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

1644번: 소수의 연속합

 

1. C++

 

#include <iostream>
#include <vector>

using namespace std;

int N;
int ans = 0;
bool primeArr[4000001];
vector<int> prime;

void Eratos(int n) {
	if (n <= 1) return;
	
	for (int i = 2; i <= n; i++) {
		primeArr[i] = true;
	}

	for (int i = 2; i * i <= n; i++) {
		if (primeArr[i]) {
			for (int j = i*i; j <= n ; j += i) {
				primeArr[j] = false;
			}
		}
	}

	for (int i = 2; i <= n; i++) {
		if (primeArr[i]) prime.push_back(i);
	}
}

void solution() {
	Eratos(N);
	int start = 0;
	int end = 0;
	int sum = 0;
	while (true) {
		if (sum >= N) sum -= prime[start++];
		else if (end >= prime.size()) break;
		else sum += prime[end++];

		if (sum == N) ans++;
	}

	cout << ans << '\n';

}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	solution();
	return 0;
}

투 포인터 부분은 동일하고

에라토스테네스 체로 소수를 찾아냈다.

 

 

2. Python

같은 방법인데 파이썬 코드로

def Eratos(n):
    primebool = [True] * (n+1)
    sqrtn = int(n**0.5)
    for i in range(2, sqrtn+1):
        if primebool[i] == True:
            for j in range(i+i, n+1, i):
                primebool[j] = False

    return [i for i in range(2, n+1) if primebool[i] == True]

def solution():
    primelist = Eratos(N)
    sum = 0
    start = 0
    end = 0
    ans = 0
    while True:
        if sum >= N:
            sum -= primelist[start]
            start += 1
        elif end >= len(primelist) : break
        else:
            sum += primelist[end]
            end += 1

        if sum == N: ans += 1
    
    print(ans, '\n')



if __name__ == "__main__":
    N = int(input())
    solution()

 

 

투 포인터

백준 온라인 저지 투포인터 문제 목록 

2003 수들의 합2  나의 풀이

1644 소수의 연속합  나의 풀이

1806 부분합 나의 풀이

2143 두 배열의 합  나의 풀이

1728 구슬 굴리기 나의 풀이

2886 Expected Allowance 나의 풀이