[백준/C++] 1644번: 소수의 연속합

문제 & 링크

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

 

풀이

1. 에라토스테네스의 체를 이용하여 4,000,000까지의 모든 소수를 구해준다. (2부터 4,000,000까지 반복문을 이용하여 탐색한다. 탐색된 수 자기 자신을 제외한 모든 배수들을 bool 타입을 이용해서 체크한다.)

2. 반복문을 마친 후 체크되지 않은 수들이 곧 소수이기에, 이를 따로 배열에 저장한다.

3. 투 포인터(i = 0, j = 1)를 이용하여 해당 인덱스에 임시 연속합(tmp)을 만든다.

4. N이 소수일 경우 cnt를 1 증가시킨다.

5. 임시 연속합(tmp)이 N보다 클 경우 임시 연속합에서 i 인덱스에 해당하는 소수를 빼고,  i를 증가시킨다.

6. 임시 연속합(tmp)이 N보다 작을 경우 j를 증가시키고, 임시 연속합에서 j 인덱스에 해당하는 소수를 더한다. 

7. 임시 연속합(tmp)과 N이 같을 경우 cnt를 1 증가시키고,  j를 증가시키고, 임시 연속합에서 j 인덱스에 해당하는 소수를 더한다. 

8. 4 - 6의 과정을 i와 j 가 같아질 때 까지 반복한다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

bool not_prime[4000001] = {false};
vector<int> V;

int main() {
    int N;
    cin >> N;
    
    not_prime[0] = true;
    not_prime[1] = true;
    
    for (int i = 2; i < 4000001; i++) {
        if (!not_prime[i]) {
            for (int j = i * 2; j < 4000001; j += i) not_prime[j] = true;
            V.push_back(i);
        }
    }
    
    int cnt = 0;
    if (!not_prime[N]) cnt++;
    
    int i = 0;
    int j = 1;
    
    int tmp = V[i] + V[j];
    while (i != j) {
        if (tmp > N) {
            tmp -= V[i];
            i++;
        }
        else {
            if (tmp == N) cnt++;
            j++;
            tmp += V[j];            
        }
    }
    
    cout << cnt;
}