[백준] 소수 사이 수열(3896)

문제 링크 : [백준] 소수 사이 수열(3896)

문제 설명

n이 주어지면, n보다 작거나 같은 소수 중 가장 큰 수와 n보다 크거나 같은 소수 중 가장 작은 소수의 차이를 구하세요.

입력

T(테스트 케이스 수)
N_i(n, 1 < N_i < 1,299,709)

5
10
11
27
2
492170

출력

4
0
6
0
114

카테고리

#에라토스테네스의 체 #이분탐색

시간 복잡도 상한

O(NlogN)

해결 방법

1. 에라토스테네스의 체로 N의 최대값보다 하나 더 큰 소수까지를 구합니다.
2. lower_bound로 N보다 크거나 같은 소수 중 가장 작은 소수(그 위치를 p라고 함)를 구합니다.
3. 그 수가 소수라면, 0을 출력합니다.
4. 그 수가 소수가 아니라면, p번째 소수와 p-1번째 소수의 차이를 출력합니다.
5. 이렇게도 풀리나, 그냥 하나씩 줄이면서, 하나씩 커지면서 소수인지를 판별하는 것이 메모리도 적게 쓰고, 시간도 빠릅니다.

시간복잡도

O(N+logN)

코드

#include<cstdio>
#include<vector>
#include<algorithm>
#define M 1299743
using namespace std;
vector<int>v;
int t,n,e[M],i,j;
int main(){
    for(i=2;i<M;i++){
        if(e[i])continue;
        v.push_back(i);
        for(j=2;i*j<M;j++)e[i*j]=1;
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        i=lower_bound(v.begin(),v.end(),n)-v.begin();
        printf("%d\n",v[i]==n?0:v[i]-v[i-1]);
    }
}

#include<cstdio>
int t,n,i,j;
int p(int x){
    for(i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        j=n;
        if(!p(n)){
            while(!p(j))j++;
            while(!p(n))n--;
        }
        printf("%d\n",j-n);
    }
}