백준 17103번 : 골드바흐 파티션 (C 언어)

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

17103번: 골드바흐 파티션

Code:

#include <stdio.h>
 
int main()
{
    int t;
    scanf("%d", &t);
    int arr[1000001] = { 0, };
    for (int j = 2; j <= 1000000; j ++)
    {
        arr[j] = j;
    }
    for (int i = 2; i <= 1000000; i++)
    {
        if (arr[i] == 0)
        {
            continue;
        }
        for (int j = 2 * i; j <= 1000000; j += i)
        {
            if (arr[j] == 0)
            {
                continue;
            }
            else
            {
                arr[j] = 0;
            }
        }
    }
    
    int n;
    while (t--)
    {
        scanf("%d", &n);
        int cnt = 0;
        for (int i = 2; i <= n; i++)
        {
            if (arr[i] + arr[n - i] == n)
            {
                cnt++;
                if (n - i == i)
                {
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt/2);
    }
}

문제풀이:

에라토스테네스의 체를 이용해서 소수를 판별하였다.

뒷부분에서는 ex) 10을 만들 때 3,7도 들어가고 7,3이런식으로 들어가기 때문에 /2를 해주었다.