백준 4134 - 다음 소수

입력받은 수보다 크거나 같은 수들 중 가장 가까운 소수를 구해야 하는 문제입니다.

입력받은 수에서 시작해 소수가 나올 때까지 소수를 판별해야 합니다.
2부터 n까지 반복하며 나눴을 때 나머지가 있는지 체크할 수도 있지만, sqrt(n)까지만 반복해도 소수인지 판별할 수 있습니다.

20을 예시로 들면

• 1x20
• 2x10
• 4x5
• 5x4
• 10x2
• 20x1

이렇게 대칭인 것을 확인할 수 있습니다.

#include <iostream>
#include <cmath>

long check_prime(long num);

int main()
{
	long n;
	long* nums;

	std::cin >> n;
	nums = new long[n];

	for (long i = 0; i < n; i++)
	{
		std::cin >> nums[i];
	}

	for (long i = 0; i < n; i++)
	{
		long j = nums[i];
		while (check_prime(j) == 0)
		{
			j++;
		}
		std::cout << j << "\n";
	}

	return 0;
}

long check_prime(long num)
{
	if (num <= 1)
		return 0;
	else if (num == 2)
		return 1;

	for (long i = 2; i <= sqrt(num) + 1; i++)
	{
		if (num % i == 0)
			return 0;
	}
	return 1;
}