백준 9020 C#) 골드바흐의 추측

짝수를 두 소수의 합으로 나타내되 차이가 가장 작은 것으로 출력하라고 한다. 상당히 어려운 조건처럼 보이지만 이는 사실 힌트에 가깝다.

 

public static class PS
{
    private static int[] nArr;
    private static bool[] isNotPrime;

    public static void Main()
    {
        //최댓값에 대하여 에라토스테네스의 체를 생성하면, 이후 반복하여 만들 필요가 없다
        int nMax = 0;
        int t;
        (int left, int right) ans;

        //입력
        t = int.Parse(Console.ReadLine());
        nArr = new int[t];

        for (int i = 0; i < t; i++)
        {
            nArr[i] = int.Parse(Console.ReadLine());
            nMax = Math.Max(nMax, nArr[i]);
        }

        //에라토스테네스의 체
        EratosSieve(nMax);

        //출력
        StreamWriter sw = new(new BufferedStream(Console.OpenStandardOutput()));

        for (int i = 0; i < t; i++)
        {
            ans = Goldbach(nArr[i]); //골드바흐 파티션
            sw.WriteLine($"{ans.left} {ans.right}");
        }

        sw.Close();
    }

    private static void EratosSieve(int size)
    {
        //에라토스테네스의 체를 구할 때는 크기의 제곱근까지만 반복하면 된다
        isNotPrime = new bool[size + 1];
        double sqrtSize = Math.Sqrt(size);

        for (int i = 2; i <= sqrtSize; i++)
        {
            if (!isNotPrime[i])
            {
                for (int j = i + i; j <= size; j += i)
                {
                    isNotPrime[j] = true;
                }
            }
        }
    }

    private static (int, int) Goldbach(int n)
    {
        //중간값에서부터 2씩 멀어져가는 식으로 계산한다
        int nMid = n / 2;
        int left, right;
        
        if ((nMid & 1) == 1 || nMid == 2) //중간값이 홀수거나 2라면 그대로 진행한다
        {
            left = right = nMid;
        }
        else //짝수라면 소수일 수 없으므로(2 제외) 1씩 더하고 빼줘야 한다
        {
            left = nMid - 1;
            right = nMid + 1;
        }

        //정답은 반드시 존재한다
        //둘 다 소수일 때만 반복이 끝난다
        while (isNotPrime[left] || isNotPrime[right])
        {
            left -= 2;
            right += 2;
        }

        //ValueTuple로 반환한다
        return (left, right);
    }
}

 

우선 에라토스테네스의 체를 사용해야 하는데 이를 테스트 케이스마다 만들 필요는 없다.

n의 최댓값을 구하고 그 크기만큼 만들어두면 모든 n에 대응할 수 있다.

 

골드바흐 파티션도 모든 경우의 수를 구할 필요가 없다.

두 소수의 차이가 가장 작은 것을 출력하라고 했는데 이는 중간값에서 출발했을 경우 처음으로 구할 수 있는 답이다.

 

중간값 n / 2로부터 거리 d만큼 떨어진 두 수 n / 2 - d와 n / 2 + d가 있다고 가정하자.

이때 두 수의 합은 항상 n이므로 거리 d를 0 혹은 1부터 2씩 늘려가며 두 수가 소수가 되는 경우를 찾기만 하면 된다.