[백준] 9020 골드바흐의 추측

9020번: 골드바흐의 추측

문제 확인

 

소수 관련 문제입니다. 범위가 10000으로 적으므로 에라토스테네스의 체 알고리즘으로 간단하게 풀 수 있습니다.

 

풀이

 

10000 이하의 수를 에라토스테네스의 채 알고리즘을 통해 소수를 미리 구해둡니다.

그 후 가장 가까운 두 소수를 찾기 위해 입력받은 수에서 2를 나눈 2개의 변수를 두고 하나는 증가, 하나는 감소하며 두 변수 모두 소수일 때 출력합니다.

 

코드

#include <cstdio>
#include <string.h>
int main(){
    int n;
    char p[10001];
    memset(p, 1, 10001);
    p[1] = 0;
    for (int i = 2; i*i <= 10000; i++)
        if (p[i])
            for (int j = i * i; j <= 10000; j += i)
                p[j] = 0;
    scanf("%d", &n);
    for (; ~scanf("%d", &n);) {
        int x = n / 2, y = x;
        while (!p[x] || !p[y]) { x--; y++; }
        printf("%d %d\n", x, y);
    }    
}