백준 g4 1644 소수의 연속합 c++

https://acmicpc.net/problem/1644

1644번: 소수의 연속합

 

문제

자연수 N이 주어질 때 연속된 소수들의 합으로 N을 만드는 가짓 수 구하기

 

풀이

1. 소수 구하기

N <= 4*10^6이므로 그냥 for문으로 구하면 시간 초과가 난다.

j*j < i일 때까지 검사하는 방법으로 소수를 구하면 O(N루트N) 이므로 시간이 간당간당하다.

 

에라토스테네스의 체를 이용하면 O(NlogN)에 구할 수 있다.

 

2. 투포인터로 연속된 소수들의 합 구하기

(https://kyj0032.tistory.com/68)

while st < N && en < N
	if sum == N
    	 ans+1
     else if sum < N
     	en++
        sum+= arr[en]
    else if sum > N
    	sum -= arr[st]
        st++

 

+ 주의할 점

N = 1부터 시작하므로 1일 때 주의

 

전체 코드

/*boj g4 1644 소수의 연속합*/
#include <iostream>
#include <vector>
#define MAXN 4000005
using namespace std;

int N;
bool isPrime[MAXN];
vector<int> primes;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    if (N == 1) {
        cout << 0 << "\n";
        return 0;
    }

    for (int i = 0; i <= N; i++)
        isPrime[i] = true;
    // 1. 소수들의 배열 구하기
    isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i] == true) {
            primes.push_back(i);

            for (int j = i * 2; j <= N; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 2. 연속된 소수들의 합 구하기
    int st = 0;
    int en = 0;

    int sum = primes[0];
    int ans = 0;
    while (st < primes.size() && en < primes.size()) {
        if (sum == N) {
            ans++;

            sum -= primes[st];
            st++;
        } else if (sum < N) {
            en++;
            sum += primes[en];
        } else { // sum > N
            sum -= primes[st];
            st++;
        }
    }

    cout << ans << "\n";
}