[C++/백준 4134번] 다음 소수

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

4134번: 다음 소수

 

 

해결 방법

유명한 소수 판별법을 사용했다. 에라토스테네스의 체를 이용해 sqrt(N) 까지만 나누어 보고 소수인지 아닌지 판별할 수 있었다.

따라서 시간 복잡도도 sqrt(N)이다.

시도해보진 않았지만 범위를 long long 이 아닌 unsigned int 로 하여도 무방할 듯 하다.

 

IsPrime 함수에서 소수를 판별하고, 소수가 아니면 값을 증가시켜 다시 검사해 소수를 찾는다.

※ for문의 i값 범위는 당연히 sqrt(N) 이하지만 양변 제곱을 통해 조건문은 i * i < = num 이 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
bool IsPrime(long long input)
{
   long long num = input;

    if(num <= 1) return false;
    if(num == 2 || num == 3) return true;
    if(num % 2== 0 || num % 3 == 0) return false;

    for(long long i = 5; i * i <= num ;i++)
    {
        if(num % i == 0) return false;
    }

    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  
    long long N;

    cin >> N;

    for(int i = 0 ; i < N ; i++)
    {
        long long input;
        cin >> input; 


        while(!IsPrime(input))
            input++;

        cout << input << '\n';
           
    }

    return 0;
}

 

참고해서 읽으면 좋을 글

 

https://makedotworld.tistory.com/13

소수 판별법, 왜 루트 N 이하의 수만 나눠보면 되는 것일까?