[백준 4134] 다음 소수 (C++)

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

문제

---

정수 n(0 ≤ n ≤ 4*10⁹)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

 

출력

---

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

 

문제 풀이

---

브루트포스 문제.

 

n부터 시작하여 1씩 더해가며 해당 수가 소수인지 확인한다. 하나의 수 i에 대해 에라토스테네스의 체처럼 2부터 sqrt(i)까지 반복문을 돌려 그 수가 i로 나누어 떨어지는지 확인해주면 된다. 나누어 떨어지면 소수가 아니므로 다음 수를 탐색하고, sqrt(i)까지 탐색했는데 i로 나누어 떨어지는 수가 없다면 해당 수가 정답이 된다.

 

0이나 1일 때는 답이 2가 나와야 하므로 2를 출력하도록 해준다.

 

아래는 코드.

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

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		long long num;
		cin >> num;
		if (num == 0 || num == 1)
		{
			cout << 2 << "\n";
			continue;
		}
		while (true)
		{
			if (isPrime(num))
			{
				cout << num << "\n";
				break;
			}
			num++;
		}
	}
	return 0;
}