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

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long T;
	cin >> T;
	
	vector<long> outputNumber; // 출력할 숫자들

	for (long i = 0; i < T; i++)
	{
		long n;
		cin >> n;

		// 0과 1은 소수가 아님
		if (n == 0 || n == 1)
		{
			outputNumber.push_back(2);
			continue;
		}

		long curNum = n;

		while (true)
		{
			bool isPrime = true;

			for (long i = 2; i <= sqrt(curNum); i++)
			{
				if (curNum % i == 0)
				{
					// 소수가 아님
					isPrime = false;
					break;
				}
			}

			if (isPrime)
			{
				// 소수인 경우
				outputNumber.push_back(curNum);
				break;
			}
			else
			{
				curNum++;
			}
		}
	}

	for (long i = 0; i < outputNumber.size(); i++)
	{
		cout << outputNumber[i] << "\n";
	}
	

	return 0;
}

---

<풀이과정>

1. 테스트케이스의 갯수 T를 입력받고, 각 출력할 숫자들을 담을 벡터 outputNumber를 long형으로 선언한다.

2. T만큼 반복하며 n을 입력받고 만약 n이 0 또는 1이라면 소수는 2부터 시작이므로 2를 출력벡터에 넣어준다.

3. 2이상의 숫자의 경우에는 입력 값 n을 curNum에 저장하고, while문을 반복하며 소수인지를 검사한다.

4. 소수인지를 판단하는 bool형 변수 isPrime을 true로 설정하고, 2부터 curNum의 제곱근까지 반복하며 curNum을 해당 수로 나누었을 때 나누어 떨어진다면 소수가 아닌 것이므로 isPrime을 false로 바꿔주고 for문을 빠져나간다.

5. 소수라면 for문이 끝날때까지 isPrime이 true 상태로 유지된다.

6. 만약 isPrime이 true로 빠져나왔다면 해당 수는 소수이므로 outputNumber에 추가해주고, isPrime이 false로 빠져나왔다면 curNum을 1 증가시켜준뒤 같은 과정을 소수가 나올때까지 반복한다.

7. 위의 과정을 모든 n에 대해 반복하면 outputNumber에 n보다 크거나 같은 소수들이 입력될 것이므로 outputNumber의 원소들을 차례로 출력해주면 된다. 

---

<코멘트>

처음에 시간초과가 나서 시간을 줄이려고 결과로 나오는 모든 수의 결과값들을 저장해서 사용했더니 메모리 초과가 나왔다.ㅋㅋㅋ 그래서 혹시나 해서 각 숫자마다의 결과를 그때그때 출력하는 코드를 짰는데 이게 정답이었다.ㅋㅋ

그리고 int형의 범위는 약 -2*10^9 ~ 2*10^9 이어서 안됐고 long형 이상으로만 가능했다.

---

<제출결과>