[4134] 다음 소수

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

• 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

• 각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

생각

정수 n의 범위가 (0 ≤ n ≤ 4*109) 이기 때문에 원래 소수를 구하던 것 처럼 풀면 분-명 시간초과가 날 것이고, 그렇기때문에 정답 비율이 25.414% 인듯 하다..

탐색 시간과 범위를 줄이기 위해서 제곱근의 개념을 사용한다고 한다. 참고
소수인지 판별할 때, 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나게 된다.
따라서 소수인지 판별할 때는 그 자연수의 제곱근 이하의 수까지만 검사를 하면 된다.
예시) √24 를 기준으로 한다 할 때

2 * 12 | 3 * 8 | 4 * 6 | √24 * √24 | 6 * 4 | 8 * 3 | 12 * 2

따라서, 소수를 판별할 때 제곱근을 이용하고, 자신보다 크거나 같은 수이기 때문에, n++을 해주며 소수판별을 진행한다.

참고로 n 범위 때문에 long으로 해야한다.

처음 코드

처음 코드는 아니긴 한데, long으로 한다 해놓고서 int로 작성해서 고침..

namespace SongE
{
    public class Program
    {
        static bool IsPrime(long x)
        {
            if (x <= 1)
            {
                return false;
            }

            if (x == 2) return true;

            for (long i = 2; i < Math.Sqrt(x) + 1; i++)
            {
                if (x % i == 0)
                    return false;
            }
            return true;
        }
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            long t = long.Parse(input.ReadLine());

            for(long i = 0; i < t; i++)
            {
                long n = long.Parse(input.ReadLine());
                while(true)
                { 
                    if (n <= 1) n++;

                    if(IsPrime(n)) 
                    { 
                        print.WriteLine(n);
                        break;
                    }
                    n++;
                }

            }
        }
    }
}