(C++) - 백준(BOJ) 3896번 : 소수 사이 수열

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

3896번: 소수 사이 수열

소수 찾기 + 이분탐색문제였습니다

 

풀이방법

 1. 100000번째 소수까지 모두 구해놓습니다. 에라토스테네스의 체 방식을 이용하면 O(루트N)으로 빠르게 구할 수 있습니다.

 

 2. 소수라면 0을 출력, 이분탐색으로 해당 수보다 큰 가장 가까운 소수에 해당하는 인덱스를 찾습니다. 그 후 해당인덱스 - (해당인덱스 - 1)의 값을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int t, ck[1300001];
vector <int> prime;

void checkPrime(){
    for(int i = 2; i <= 1300000; i++){
        if(ck[i]) continue;
        for(int j = i+i; j <= 1300000; j+=i) ck[j] = 1;
    }
}

void makePrime(){
    for(int i = 2; i <= 1300000; i++){
        if(!ck[i]) prime.push_back(i);
    }
}

int binarySearch(int key){
    int l = 2;
    int r = prime.size() - 1;
    while(l<=r){
        int mid = (l+r) / 2;
        if(prime[mid] >= key) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

int main(){
    cin >> t;
    checkPrime();
    makePrime();
    while(t--){
        int k;
        cin >> k;
        if(!ck[k]) cout << 0 << '\n';
        else {
            int idx = binarySearch(k);
            cout << prime[idx] - prime[idx-1] << '\n';
        }
    }
}