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

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

 

문제를 요약하자면 어떤 수 N의 값이 2보다 큰 짝수라면 두 소수의 합으로 나타낼 수 있다는 것이 골드바흐 수라고 한다. 다만 여기서 두 소수가 여러가지인 경우가 있는데 (예를 들면 14의 경우 3, 11 도 가능하고 7, 7 도 가능하다.) 이럴 경우에는 두 수의 값이 최소인 경우를 출력하는 것이 문제이다.

 

소수 찾는 공식은 이전 포스트에서도 계속 다뤄왔는데, 문제는 두 소수의 합을 나타내는 것과, 두 수의 값이 최소인 경우를 찾는 것이 문제이다.

 

두 소수의 합

두 소수의 합을 구하는 공식은 간단하다. N이라는 수가 있다면, 이전에 에라토스테네스의 체 알고리즘을 통한 소수를 모두 구해뒀다면, 반복하면서 N - i의 값이 소수인지를 판별하면 된다.

 

모든 골드바흐 수 출력

using System;

class Program
{
    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());

        List<int> list = new List<int>();

        for(int i = 0; i < T; i++)
        {
            list.Add(int.Parse(Console.ReadLine()));
        }

        foreach(int num in list)
        {
            bool[] isPrime = new bool[num + 1];

            for (int i = 2; i <= num; i++)
            {
                isPrime[i] = true;
            }

            for(int i = 2; i * i <= num; i++)
            {
                if (isPrime[i])
                {
                    for(int j = i * i; j <= num; j+=i)
                    {
                        isPrime[j] = false; 
                    }
                }
            }

            
            for(int i = 2; i <= num; i++)
            {
                if (isPrime[i] && isPrime[num - i])
                {
                     Console.WriteLine($"{i} {num - i}");
                }
            }

        }


    }
}

 

 

모든 골드바흐 수를 출력하는 것은 위처럼 num만큼 반복하여 조건에 i가 소수이며, num - i도 소수라면 이 두 수 를 출력해주면 된다.

 

다만 여기서 문제는 두 수의 차이가 최소여야 한다는 것이다.

 

두 수의 차이가 최소인 골드바흐의 수

이는 num을 2로 나누어서 i로 두고, 위에서부터 반복해나가면서 i--를 반복해주면 된다.

 

이게 무슨뜻이냐, 어렸을 때 1부터 100사이의 수 중 무작위로 선택하여 이를 업 다운으로 찾아가는 게임을 해봤을 것이다.

 

이 게임의 공략은 반으로 줄여나가면서 타겟을 좁혀나가는 것이다. 즉 50, 25 이런식으로 줄여서 업다운을 찾는 방법이다.

 

위와 비슷한 논리인게 예를 들어 20의 경우 나누었을 때 10이며 여기서부터 반복하여 내려갔을 경우 가장 먼저 나오는 소수와 나머지 수의 차이가 가장 최소인 것이다.

 

 

using System;

class Program
{
    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());

        List<int> list = new List<int>();

        for(int i = 0; i < T; i++)
        {
            list.Add(int.Parse(Console.ReadLine()));
        }

        foreach(int num in list)
        {
            bool[] isPrime = new bool[num + 1];

            for (int i = 2; i <= num; i++)
            {
                isPrime[i] = true;
            }

            for(int i = 2; i * i <= num; i++)
            {
                if (isPrime[i])
                {
                    for(int j = i * i; j <= num; j+=i)
                    {
                        isPrime[j] = false; 
                    }
                }
            }

            // 골드바흐 파티션 (최소)
            int a = 0; int b = 0;
            for(int i = num / 2; i >= 2; i--)
            {
                if (isPrime[i] && isPrime[num - i])
                {
                    a = i;
                    b = num - i;
                    break;
                }
            }

            Console.WriteLine($"{a} {b}");

        }


    }
}