9020번: 골드바흐의 추측

#include<cstdio>

#define max 20000

int main()

{

int t, n, up, down;

scanf("%d", &t);

bool num[max+1];

for (int i = 0; i <= max; ++i)

num[i] = 1;

for (int i = 4; i <= max; i += 2)

num[i] = 0;

for (int i = 3; i*i <= max; i += 2)

if (num[i] == 1)

for (int j = i*i; j <= max; j += 2 * i)

num[j] = 0;

while (t--)

{

scanf("%d", &n);

up = down = n / 2;

while (up > 1 && down < 20001)

if (num[up] == 1 && num[down] == 1 && up + down == n)

break;

else if (up + down >= n)

for (--down; num[down] != 1; --down);

else

for (++up; num[up] != 1; ++up);

printf("%d %d\n", down, up);

}

}

===============위에는 down변수 사용. 그렇게 할 경우 범위가 커지는 다른 문제에서 시간 초과이기에 아래와같이 바꿔주면 좀 더 범용적임.

#include<cstdio>

#define max 20000

int main()

{

int t, n, up;

scanf("%d", &t);

bool num[max + 1];

for (int i = 0; i <= max; ++i)

num[i] = 1;

for (int i = 4; i <= max; i += 2)

num[i] = 0;

for (int i = 3; i*i <= max; i += 2)

if (num[i] == 1)

for (int j = i*i; j <= max; j += 2 * i)

num[j] = 0;

while (t--)

{

scanf("%d", &n);

up = n / 2;

while (up <= n)

if (num[up] == 1 && num[n - up] == 1)

break;

else

for (++up; num[up] != 1; ++up);

printf("%d %d\n", n - up, up);

}

}