🖊️ 문제

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

--

🖊️ 풀이

처음에 에라토스테네스의 체를 쓰려고 했는데,
정수 한도가 너무 커서 오히려 그게 더 오버였다.

커봤자 루프 몇 번 안도는 알고리즘일 것 같아서,
그냥 n부터 결과 나올 때까지 완전탐색으로 돌렸다.

그리고 소수 판별할 때,
그냥 2 ~ n을 루프돌면 시간초과뜬다.

기본적으로 제곱근에 대해 루프도는 걸로 반드시~!

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

bool IsSosu(ll n)
{
	if (n < 2) return false;
	int sqrtN = sqrt(n);
	for (ll i = 2; i <= sqrtN ; i++)
		if (n % i == 0) return false;
	return true;
}

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

	int tk;
	cin >> tk;
	for (int t = 0; t < tk; t++) {
		ll n;
		cin >> n;
		while (!IsSosu(n)) {
			n++;
		}
		cout << n << '\n';
	}
}