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

[ 문제 ]

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

[ 코드 ]

1. 내 코드

using System.Text;

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();

int T = int.Parse(sr.ReadLine());

for (int i = 0; i < T; i++)
{
    int n = int.Parse(sr.ReadLine());
    sb.AppendLine($"{PrimeNum(n)}");
}

sw.Write( sb.ToString() );
sw.Flush();
sw.Close();
sr.Close();


int PrimeNum(int n)
{
    int count = 0;

    for (int i = 2; i <= n / 2; i++)
    {
        if (IsPrime(i) && IsPrime(n - i))
        {
            count++;
        }
    }
    return count;
}

bool IsPrime(int i)
{
    if (i <= 1) return false;
    else if (i <= 3) return true;
    else if (i % 2 == 0 || i % 3 == 0) return false;

    for (int j = 5; j * j <= i; j += 6)
    {
        if (i % j == 0 || i % (j + 2) == 0) return false;
    }

    return true;
}

 

2. 다른 사람 코드

namespace Programe
{
    public static class Programe
    {
        static void Main(string[] args)
        {
            int t = Convert.ToInt32(Console.ReadLine());
            List<int> primes = new List<int>();
            bool[] check = new bool[1000001];

            for (int i=2; i <=1000000;i++)
            {
                if (check[i] == false) {
                    primes.Add(i);
                    for (int j = i+i; j<=1000000;j+=i) {
                        check[j] = true;
                    }
                }
            }

            while (t-- > 0)
            {
                int n = Convert.ToInt32(Console.ReadLine());
                int ans = 0;
                foreach (int p in primes)
                {
                    if (n-p >= 2 && p <= n-p) {
                        if (check[n-p] == false) {
                            ans += 1;
                        }
                    }
                    else {
                        break;
                    }
                }
                Console.WriteLine(ans);
            }
        }
    }
}

 

[ 실행화면 ]

case: 1

 

 

 

 

 

---

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

17103번: 골드바흐 파티션