[Baekjoon] 4134번: 다음 소수

 

 

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

4134번: 다음 소수

 

---

 

문제 해결 과정

착안

소수를 빠르게 찾기하기 위한 유명한 알고리즘 중의 하나로 에라토스테네스의 체(Sieve of Eratosthenes) 라는 것이 있는데, 해당 알고리즘은 2 이상의 자연수부터 시작하여 어떤 자연수 $n \space (n \geq 2)$ 까지의 수들이 소수인지 아닌지를 판단하는 데에 유리한 방법이다.

 

그러나 위의 방법은 구하고자 하는 소수가 $n$보다 큰 경우에 활용하기가 어렵기 때문에 다른 방법을 이용하여 문제를 해결하고자 하였다.

* 소수가 존재할 것으로 예상되는 만큼을 어림잡아서 문제를 해결할 수 있기는 하나 적절한 방법은 아니라고 판단함.

 

소수를 판정하기 위한 마땅한 방법이 생각나지 않아 브루트 포스(brute force) 알고리즘을 사용하여 문제를 해결하고자 하였다. 이때 연산량을 줄이기 위해 다음과 같은 수의 성질을 이용하였다.

 

• 2 이상의 자연수 $n$에 대하여, $k \neq n$ 인 자연수 $k$ 가 $n$의 약수이면 $n / k$도 $n$의 약수이다.

 

위와 같은 성질에 의해, $n$이 2 이상의 자연수로 나누어지는지 판단하는 과정을 $\sqrt{n}$ 까지만 수행해보면 주어진 자연수 $n$이 소수인지 판단할 수 있다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(size_t n)
{
	if (n < 2)
		return false;

	for (size_t i = 2; i <= (size_t)sqrt(n); i++)
		if (!(n % i) && n != i)
			return false;

	return true;
}

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

	int T;
	cin >> T;

	while (T--)
	{
		size_t N;
		cin >> N;

		while (!IsPrime(N++));
		cout << N - 1 << "\n";
	}

	return 0;
}

 

실행 결과