백준 C# - 17103 +) 풀이

이 문제를 알기 앞서 에라토스테네스의 체를 알아야 한다. 그래서 아래 문제를 먼저 풀고 오는 것을 추천한다.

백준 C# - 1929

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

---

01 에라토스테네스의 체

위의 링크에 에로트세테스의 체에 관련된 설명을 확인할 수 있다.

bool[] isPrime = Enumerable.Repeat(true, 1000000 + 1).ToArray();
for (int i = 2; i * i <= 1000000; i++)
{
    if (isPrime[i])
    {
        for (int j = i * i; j <= 1000000; j += i)
        {
            isPrime[j] = false;
        }
    }
}

---

02 골드 바흐 파티션

골드 바흐의 추측은  2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 그러므로 합을 이용해서 두 수가 소수인지 확인해보고 둘 다 소수인 경우 count를 증가시킨다.

for (int j = 2; j <= n/2; j++)
{
    if (isPrime[j] && isPrime[n - j])
        count++;
}

 

---

코드 전문

using System;
using System.Linq;

namespace baek2
{
   
    class Program
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());           
            bool[] isPrime = Enumerable.Repeat(true, 1000000 + 1).ToArray();

            for (int i = 2; i * i <= 1000000; i++)
            {
                if (isPrime[i])
                {
                    for (int j = i * i; j <= 1000000; j += i)
                    {
                        isPrime[j] = false;
                    }
                }
            }
            for (int i = 0; i < t; i++)
            {
                int count = 0;
                int n = int.Parse(Console.ReadLine());
                for (int j = 2; j <= n/2; j++)
                {
                    if (isPrime[j] && isPrime[n - j])
                        count++;
                }
                Console.WriteLine(count);
            }
        }
    }
}