[C++] 백준 4134: 다음 소수

문제 이해

- 정수 n이 주어졌을 때 n이상인 소수를 출력하라.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 128MB

 

<입력>

T: 테스트 케이스 개수

n: 정수 (0 ~ 4 * 10^9)

 

<출력>

각각의 테스트 케이스에 대하여 n 이상인 소수를 출력하라.

 

 

---

문제 풀이

처음에는 소수 문제라서 에라토스테네스의 체를 생각했는데

n의 최댓값이 4 * 10^9으로 메모리 제한에 걸릴거 같았다.

 

 

다음으로 생각한게 1부터 n까지 탐색하는 완전 탐색인데

이 방법 역시 O(n)의 시간복잡도로는 시간초과일것 같았다.

 

 

결국 인터넷을 참고하여 풀었는데

핵심은 바로 이것이다.

어떠한 값에 대하여 소수를 판단할 때, 그 값의 약수들의 곱은 그 값의 제곱근을 기준으로 대칭이기 때문에
제곱근 이하의 값 까지만 검사를 하면 나머지는 검사를 할 필요가 없다

 

즉, sqrt(n)까지만 검사하면 되는 것이다.

 

 

---

전체 코드

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        if(n >= 0 && n <= 2){
            cout<<2<<"\n";
        }else if(n == 3){
            cout<<3<<"\n";
        }else{
            while(!isPrime(n)){
                n++;
            }
            cout<<n<<"\n";
        }
    }
    
    return 0;
}

 

 

 

---

배운 점

소수를 판정할 때 약수의 성질을 이용하여 제곱근까지만 탐색하면 된다는 걸 배울 수 있었다!