백준 C# - 6588 +) 풀이

문제를 풀기 앞서 아래 문제를 먼저 푸는 것을 추천한다.

백준 C# - 1929

백준 C# - 1929 +) 에라토스테네스의 체

---

풀이

01 에라토스테네스의 체 알고리즘 사용

상세 설명은 위의 문제에서 확인

StringBuilder sb = new StringBuilder();
int num = -1;
bool[] isPrime = Enumerable.Repeat(true, 1000000 + 1).ToArray();
int[] prime = new int[1000001];
int index = 0;
for (int i = 2; i * i <= 1000000; i++)
{
    if (isPrime[i])
    {
        prime[index] = i;
        index++;
        for (int j = i * i; j <= 1000000; j += i)
        {
            isPrime[j] = false;
        }
    }
}

---

02 두 소수 찾기

while (num != 0)
{
    num = int.Parse(Console.ReadLine());
    int a = 0;
    int b = 0;
    if (num == 0)
        break;
    for (int i = 0; i <= num / 2; i++)
    {
        a = prime[i];
        b = num - a;
        if (isPrime[a] && isPrime[b])
        {
            sb.AppendLine($"{num} = {a} + {b}");
            break;
        }
    }
}

 

왜 i <= num이 아니라 i <= num / 2인가요?

for (int i = 0; i <= num / 2; i++)

 

그 이유는 크리스티안 골드바흐에 따르면 4 이상의 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 짝수 num을 두 홀수 소수의 합으로 나타낼때 하나의 홀수 소수는 num / 2 이하의 값을 가지고 나머지 값을 또 다른 소수로 채우면 된다. 

그러므로 num / 2까지만 구하면 된다.

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace baek2
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            int num = -1;
            bool[] isPrime = Enumerable.Repeat(true, 1000000 + 1).ToArray();
            int[] prime = new int[1000001];
            int index = 0;
            for (int i = 2; i * i <= 1000000; i++)
            {
                if (isPrime[i])
                {
                    prime[index] = i;
                    index++;
                    for (int j = i * i; j <= 1000000; j += i)
                    {
                        isPrime[j] = false;
                    }
                }
            }

            while (num != 0)
            {
                num = int.Parse(Console.ReadLine());
                int a = 0;
                int b = 0;
                if (num == 0)
                    break;
                for (int i = 0; i <= num / 2; i++)
                {
                    a = prime[i];
                    b = num - a;
                    if (isPrime[a] && isPrime[b])
                    {
                        sb.AppendLine($"{num} = {a} + {b}");
                        break;
                    }
                }
            }
            Console.WriteLine(sb.ToString());
        }
    }

}