Boj 3896 c++ 소수사이 수열

소수에 관련된 문제에 재미가 들려서 문제를 계속 푸는 중이다. 이 문제는 어떤 수가 주어졌을 때 그 수가 포함된 소수사이 수열의 길이를 출력하는 프로그램이다.
 
이문제를 풀면서 깨달은 점은 2가지이다.
 
첫번째, 벡터를 크게 사용했을 때 메모리초과, 시간초과가 발생하는 것은 벡터의 크기 때문이 아니라는 것. 전역변수로 선언하면 자유롭게 매우 큰 형태로 생성할 수 있다는 것.
 
그리고 두번째는 이분탐색이 이루어지는 구조를 정확히 알 필요가 있다는 점, 두가지였다.
 
우선은 이분탐색을 통해 가장 소수가 아닌 수 k보다 큰 가장 작은 소수를 구하는 방법이 떠오르지 않아 구글링을 했다.
코드는 다음과 같다.

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

using namespace std;
vector<bool> v(1299710, 1);
vector<long long> prime;

int main(){

    int n, k;

    cin>>n;

    v[0]=v[1]=0;

    for(int i=0; i*i<=1299710; i++){
        if(v[i]==1){
            for(int j=i*i; j<=1299710; j+=i){
                v[j]=0;
            }
        }
    }
    for(int i=2; i<1299710; i++){
        if(v[i]==1)
            prime.push_back(i);
    }

    while(n--){
    cin>>k;
    if(v[k]==1){
        cout<<"0"<<"\n";
    } else {

        int head=0, tail=prime.size()-1;
         int prime1;

        while(head<=tail){
            int mid=(head+tail)/2;
            if(k<=prime[mid])
                tail=mid-1;
            else
                head=mid+1;
        }prime1=head;

        cout<<prime[prime1]-prime[prime1-1]<<"\n";
    }


}

}

 

우선은 에라스토테네스의 체를 이용하여 범위 내의 소수를 모두 구하여 prime이라는 벡터에 집어넣어 주었다. 그후, 배열의 크기 만큼 이분탐색을 해주었다. 이때,  입력 k를 기준으로 시작값과 끝값을 조정하여 점점더 탐색범위를 좁혀나갔다. 이때, 탐색종료조건이 head>tail이므로 탐색이종료되었을 시점, head 인덱스가 가리키고 있는 값은 k보다 큰 최소의 소수 값이다. 그리고 k보다 작은 최대의 소수 인덱스는 head-1이므로 이를 계산하여 출력하면 된다.  이제부터는 수학, 정렬, 구현 만으로 풀 수 있는 문제가 거의 없기 때문에 그리디 알고리즘, 그래프 탐색에 대한 문제를 풀어볼 예정이다.