4134번: 다음 소수

 

- 관련 사이트: https://www.acmicpc.net/problem/4134

4134번: 다음 소수

 

정수 n 이 주어졌을 때, n 보다 크거나 같은 소수 중 가장 작은 소수 찾는 문제이다.

 

1) 입력된 수부터 약수인지 확인

2) 2부터 수의 제곱근까지 나눠지는 수가 있는지 확인: i * i <= num

3) 약수가 없다면 소수이므로 출력

 

#include <iostream>
using namespace std;

bool isPrime(long long int num)
{
    if (num <= 1) 
        return false;

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

int main()
{
    long long int T, n;
    cin >> T;
    
    for (long long int i = 0; i < T; i++)
    {
        cin >> n;
        while (!isPrime(n))
            n++;
        cout << n << "\n";
    }
    return 0;
}

- 메모리: 2020 KB

- 시간: 288 ms

- 코드 길이: 463 B