[BOJ] 소수 사이 수열_3896 C++ 풀이

문제

소수 사이 수열

접근방법

입력되는 정수 k보다 크면서 가장 가까운 소수값을 찾는것이 이번 문제의 관건이었다. 때문에 소수 여부를 판단해 주는 isPrime함수를 선언하여 1 ~ 1299709 까지의 값 중 소수인 값만을 벡터 prime에 저장해 주었다.

만약 k가 소수이면 바로 0을 출력하고

k가 합성수라면 lower_bound함수를 사용하여 k보다 크면서 가장 가까운 소수의 인덱스 값을 알아내어 해당 인덱스의 소수값 ans2 = prime[idx]과 그 바로앞의 인덱스의 소수값 ans1 = prime[idx-1]을 구한 후

두 수의 차를 구해서 k를 포함하는 소수 사이 수열의 길이를 구할 수 있었다.

구현

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> prime;

bool isPrime(int num)
{
    if(num == 2) return true;
    if(num%2 == 0) return false;
    for(int i=3; i<sqrt(num)+1; i++)
    {
        if(num%i == 0) return false;
    }
    return true;
}

int main(void)
{
    int tc, k;
    int ans1, ans2;
    int idx;

    for(int i=1; i<=1299709; i++)
    {
        if(isPrime(i)) prime.push_back(i); 
    }

    cin>>tc;
    while(tc--)
    {
        ans1=ans2=0;
        cin>>k;
        if(isPrime(k))
        {
            cout<<0<<'\n';
            continue;
        }

        idx = lower_bound(prime.begin(), prime.end(), k) - prime.begin();
        ans1 = prime[idx-1];
        ans2 = prime[idx];
        
        cout<<ans2-ans1<<'\n';
    }
    return 0;
}