4134번: 다음 소수 [C++]

문제

 

 

풀이

제곱근 판별법을 통해 주어진 수 n과 크거나 같은 소수 중 가장 작은 소수를 찾아 출력하였다.

#include <iostream>
#include <algorithm>

using namespace std;

bool isPrime(unsigned int n) {
	for (unsigned int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;

	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;

	cin >> n;

	for (int i = 0; i < n; i++) {
		unsigned int num;

		cin >> num;

		if (num < 2) num = 2;
		else {
			while (true) {
				if (isPrime(num) == true) break;
				num++;
			}
		}

		cout << num << "\n";
	}

	return 0;
}