백준 문제풀기 [#9020번] - 골드바흐의 추측

위 문제는 두 소수의 차이가 가장 작은 두 값을 출력하는 것이 관건이다.

다량의 소수를 한꺼번에 판별해서 구해야 할 경우 많은 숫자들을 소수인지 하나씩 판별하다보면

실행 시간은 한없이 길어질 것입니다. 

 

 

골드바흐의 추측은 에라토스테나스의 체 개념을 이용하여 문제를 푸는 것이 간단하다. 

 

에라토스테나스의 체 

소수를 판별하는 알고리즘으로 가장 효율적인 알고리즘이다. 
가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고,
이후에 하나씩 지워나가는 방법을 이용한다.

 

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
   (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

 

 

 

위 문제에 에라토스테네스의 체 개념을 적용하여 문제를 풀어볼 것인데,

 

---

1. 0부터 10000의 숫자가 들어있는 10000개의 배열을 만들고 0과 1의 자리는 False로, 2~9999까지의 자리는 True로 세팅해준다. 

2. 2부터 반복문을 사용하여 자기 자신을 제외한 그 다음 배수부터 배열의 True를 False로 바꾸어준다. 

3. 이 후 테스트 케이스의 개수를 입력받는다. 

4. 입력받은 개수만큼 반복문을 돌리고, 반복문 안에 입력받은 짝수 n을 2로 나눈 후 두 변수 a,b에 값을 넣어준다 .

(2로 나눈 이유는 입력받은 짝수 n의 반절을 기준점으로 한쪽은 -1 을 하면서, 한쪽은 +1을 해가면서 소수를 찾아 두 소수의 가장 차이가 적은 값을 찾기 위해서이다.) 

5. 2로 나눈 짝수 (예를 들어 n/2) 를 기준점으로, n/2가 소수 배열의 값이 True라면 값을 출력, 배열의 값이 False라면 -1 , +1을 하여 다시 반복문을 실행한다. 

 

 

구현된 코드

# 9020 골드바흐의 추측

def GoldBach():
    check = [False, False] + [True] * 10000

    for i in range(2, 101):
        for j in range(i + i, 10001, i):
            check[j] = False

    n = int(input())
    for z in range(n):
        m = int(input())

        a = m // 2
        b = a

        for _ in range(5000):
            if check[a] and check[b]:
                print(a, b)
                break
            a -= 1
            b += 1


GoldBach()