[C++] 백준 3896 - 소수 사이 수열

문제 - 소수 사이 수열 (Silver1)

[백준 3896] https://www.acmicpc.net/problem/3896

풀이 전략

• 문제 해석
  1. 입력값이 소수가 아니면 입력값을 포함하고 있는 구간의 크기를 출력
  ex) input = 15 -> 15보다 작은 소수 13 & 15보다 큰 소수 17 사이의 값 4 출력
  2. 입력값이 소수이면 0 출력
• 소수 문제이기 때문에 에라토스테네스의 체로 걸러준 다음 소수들만 따로 배열에 저장한 뒤, 입력값과 비교

참고

[Lower_bound]

이 문제에서는 Lower_bound가 쓰였다. algorithm 헤더파일에 있는 함수이고, 정렬되어 있는 배열 내에서 찾고자 하는 값보다 크거나 같은 값 중 가장 처음 나오는 값의 반복자를 반환한다.

lower_bound(arr.begin(), arr.end(), value)

int index=0;
index=lower_bound(arr.begin(),arr.end(),value)-arr.begin();

[Upper_bound]

Upper_bound는 찾고자 하는 값보다 큰 값 중 처음 나오는 값을 반환하는 함수로 사용 방법은 Lower_bound랑 똑같다.
Lower_bound와 다른 점은 lower_bound는 upper_bound에서 찾고자 하는 값과 같은 경우가 더해진 것뿐이다.

upper_bound(arr.begin(), arr.end(), value)

int index=0;
index=upper_bound(arr.begin(),arr.end(),value)-arr.begin();

소스 코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

#define MAX_NUM 1299709
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    vector<int> A(MAX_NUM+1,1); 
    // 에라토스테네스의 체로 소수와 합성수를 구분할 vector A
    A[0]=A[1]=0;

    vector<int> B(N); // 입력값을 저장할 vector B
    for(int i=0;i<N;i++){
        cin>>B[i];
    } 

    vector<int> C;
    // vector A에서 소수에 해당하는 수만 저장해 놓을 vector C
    for(int i=2;i<sqrt(MAX_NUM);i++){
        if(A[i]==1){
            for(int j=i*i;j<=MAX_NUM;j+=i){
                A[j]=0;
            }
        }
    } // 에라토스테네스의 체
    for(int i=0;i<A.size();i++){
        if(A[i]==1){
            C.push_back(i);
        }
    } // A에서 소수만 C에 복사
    
    for(int i=0;i<N;i++){
        if(A[B[i]]==1){
            cout<<"0"<<'\n';
        } // 입력값이 소수이면 0 출력
        else{
            int idx=lower_bound(C.begin(),C.end(),B[i])-C.begin();
            cout<<C[idx]-C[idx-1]<<'\n';
        }
        // 입력값이 소수가 아니면 구간의 크기 출력
    }
}

결과