[C#] 17103번: 골드바흐 파티션

목차

---

백준 단계별로 풀어보기

25.11.12

15단계: 약수, 배수와 소수 2

17103번: 골드바흐 파티션

문제 링크 : https://www.acmicpc.net/problem/17103

 

문제를 풀기 위해 알아야 할 개념

>> 소수 판별 함수

: 아래 글에 정리해두었다.

 

 

소수 판별 함수 만들기

 

>> 에라토스테네스의 체

: 수학에서 특정 범위 내의 소수를 판별할 때, 가장 빠르고 쉬운 방법이다.

--> 1부터 n 까지의 소수를 알고 싶다면 합성수의 특성에 의해 n = a × b 라면, a와 b 중 적어도 하나는 √n 이하이므로 √n 이하의 소수의 배수를 지우고 남은 수가 소수이다.

 

- 소수를 구하는 과정

: 아래 과정은 1부터 120까지의 소수를 찾는 과정이다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (아래 이미지에서 회색)
2. 2는 소수이므로 오른쪽에 2를 쓰고, 2를 제외한 2의 배수를 모두 지운다. (아래 이미지에서 빨간색)
3. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓰고, 3을 제외한 3의 배수를 모두 지운다. (아래 이미지에서 초록색)
4. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓰고, 5를 제외한 5의 배수를 모두 지운다. (아래 이미지에서 파란색)
5. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓰고, 7을 제외한 7의 배수를 모두 지운다. (아래 이미지에서 노란색)
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 이를 오른쪽에 쓴다. (아래 이미지에서 보라색)

--> 이 예시의 경우, 11² > 120 이므로 11보다 작은 소수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

※ 이해를 위한 이미지

출처 : 위키백과 - 에라토스테네스의 체

 

※ 참고 문서 - 위키백과

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

- 코드

1. Enumerable.Repeat() 을 통해 isPrime 배열의 모든 값을 true로 만들어서 초기화한 다음, 0과 1은 소수가 아니므로 값을 false로 바꾼다.
2. for 반복문을 통해 2부터 √num 까지 반복하여 isPrime[i] 값이 true 라면 i × i 부터 시작하여 모든 배수의 배열값을 false로 바꾼다.
   •     i × i 부터 시작하는 이유는 i 의 배수 i × k 에 대해 k < i 인 경우는 이미 앞의 과정에서 이미 지워져있기 때문이다.
   •     ex) i = 5 일 때, 5 × 2 = 10 은 2를 처리할 때, 5 × 3 = 15 는 3을 처리할 때, 5 × 4 = 20 은 4를 처리할 때 이미 false 가 되어있다.
3. 찾은 소수 배열을 반환한다.

using System.Linq;

private bool[] IsPrime(int num)
{
    bool[] isPrime = Enumerable.Repeat(true, num + 1).ToArray();
    isPrime[0] = isPrime[1] = false;

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

 

※ 공식 문서 - Enumerable.Repeat

Enumerable.Repeat<TResult>(TResult, Int32) 메서드 (System.Linq)

 

문제 풀이

: 문제의 시간제한이 0.5초이므로, 시간을 줄이기 위해 우선 정수 N의 최댓값인 1,000,000 까지의 모든 소수를 찾아서 HashSet에 저장해둔다. 그리고 두 소수의 순서만 다른 것은 같은 파티션이기 때문에 소수 a, b 에 대해 입력값 N = a + b 이라면, a ≤ N/2 까지만 반복하면서 a와 N - a 가 모두 HashSet에 있는지 확인하면 된다.

1. StreamReader로 입력값을 받아 int값으로 변환하여 테스트 케이스의 개수를 담을 변수 t 에 담는다.
2. 찾은 소수를 담을 HashSet인 primeHash 를 초기화하고 for 반복문을 통해 2부터 정수 N의 최댓값까지 반복하면서 만든 소수 판별 함수를 통해 모든 소수를 primeHash 에 추가한다. --> 가장 작은 소수가 2이므로 2부터 시작하고, 2 외에 짝수는 소수일 수 없으므로 반복할 때 1,000,000는 포함하지 않아도 된다.
3. for 반복문을 통해 각각의 테스트 케이스마다 골드바흐 파티션의 수를 찾는다.
   •     StreamReader로 입력값을 받아 int값으로 변환하여 정수 N을 담을 변수 input 에 담고, 골드바흐 파티션의 수를 담을 변수 result 를 0으로 초기화한다.
   •     for 반복문을 통해 2부터 input / 2 까지 반복하면서 j 와 input - j 가 모두 primeHash 에 있다면 골드바흐 파티션에 해당하므로 result 를 1 증가시킨다.
   •     result 값을 StringBuilder에 담는다.
4. StreamWriter로 StringBuilder에 담은 값을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        int t = int.Parse(sr.ReadLine());
        HashSet<int> primeHash = new HashSet<int>();

        for (int i = 2; i < 1000000; i++)
        {
            if (IsPrime(i))
            {
                primeHash.Add(i);
            }
        }

        for (int i = 0; i < t; i++)
        {
            int input = int.Parse(sr.ReadLine());

            int result = 0;
            for (int j = 2; j <= input / 2; j++)
            {
                if (primeHash.Contains(j) && primeHash.Contains(input - j))
                    result++;
            }

            sb.AppendLine(result.ToString());
        }
        sw.Write(sb.ToString());
    }

    static bool IsPrime(int num)
    {
        if (num == 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        
        int limit = (int)Math.Sqrt(num);

        for (int i = 3; i <= limit; i += 2)
        {
            if (num % i == 0) return false;
        }
        return true;
    }
}

 

└ 에라토스테네스의 체 사용버전

: 에라토스테네스의 체를 사용하여 소수를 판별하는 함수 IsPrime() 을 만들어서 사용하였다.

 

>> 코드

using System.IO;
using System.Text;
using System.Linq;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        int t = int.Parse(sr.ReadLine());
        bool[] isPrime = IsPrime(1000000);

        for (int i = 0; i < t; i++)
        {
            int input = int.Parse(sr.ReadLine());

            int result = 0;
            for (int j = 2; j <= input / 2; j++)
            {
                if (isPrime[j] && isPrime[input - j])
                    result++;
            }

            sb.AppendLine(result.ToString());
        }
        sw.Write(sb.ToString());
    }

    static bool[] IsPrime(int num)
    {
        bool[] isPrime = Enumerable.Repeat(true, num + 1).ToArray();
        isPrime[0] = isPrime[1] = false;

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