BaekJoon 9020번: 골드바흐의 추측 (Python)

---

1. Problem

---

2. Solution

# prime number 판별
def is_prime(n):
    i = 5
    if n % 2 == 0:   # 2의 배수 제외
        return n == 2   # n == 2이면 True, n != 2이면 False를 return
    if n % 3 == 0:   # 3의 배수 제외
        return n == 3   # n == 3이면 True, n != 3이면 False를 return
    while i * i <= n:
        if n % i == 0:   # n을 i로 나눴을 때 나머지가 0인 경우
            return False   # False를 return
        i += 2
    return n != 1   # n != 1이면 True, n == 1이면 False를 return


bloom = [True] * 10001   # True이면 소수, False면 합성수
bloom[0] = False   # 0과 1은 쓰이지 않지만 편의상 사용
bloom[1] = False   # 0과 1번째 index만 False로 변경
for i in range(2, 10001):
    if bloom[i] and is_prime(i):   # bloom[i]와 is_prime(i)가 모두 True이면
        j = 2
        while j * i < len(bloom):   # j * i < len(bloom)이 True일 동안 반복
            bloom[j * i] = False
            j += 1

T = int(input())
for _ in range(T):
    n = int(input())
    mid = n // 2   # n의 중간 값
    for i in range(mid, 1, -1):   # 중간 값부터 2까지 -1씩 감소
        if bloom[i] and bloom[n - i]:   # bloom[i]와 bloom[n-i] 모두 True이면
            print(i, n - i)   # i와 n-i 출력
            break   # for문 종료

---

3. Detail

에스토스테네스의 체 algorithm 사용

• 변수와 함수 이름 지정 Tip
  변수명은 명사형, 함수명은 동사형으로 설정 ex) 변수명 -> prime, 함수명 -> is_prime(a)
  + 함수명 설정할 때 is_prime 처럼 동사와 명사를 "_"(underbar)로 구분해주는 것이 좋다.

• Prime number를 판별하는 함수 is_prime(n)을 작성할 때 2의 배수와 3의 배수를 제외시켜주면 while문으로 반복되어야하는 횟수의 약 66%가 줄어드므로 효율적이다. 5의 배수는 2와 3의 배수를 제외시킨 후에는 아주 작은 비율을 차지하므로 굳이 제외시키지 않아도 무방하다. i는 5부터 시작하도록 설정하고, 2의 배수를 거르기 위해 n % 2 == 0이면 2의 배수 중 2만 prime number이므로 return에 n == 2라는 조건을 걸어주어 n == 2인 경우는 True를 return, n !=인 경우는 False를 return한다. 3의 배수도 2의 배수를 제외시킨 것과 같은 방법으로 제외시키면 된다. 2의 배수와 3의 배수 이외의 정수일 경우 n % i == 0이면 False를 return하고, n % i == 0을 만족하는 경우가 없어 while문이 끝까지 반복된 후에는 n != 1이면 True를 return 한다.

• 제곱 연산인 i ** 2보다 곱 연산인 i * i가 연산이 훨씬 빠르므로 제곱 연산자 '**'보다 곱 연산자 '*'를 이용하여 식을 표현하는 것이 더욱 효율적이다.

• 반복문의 종류에는 for문과 while문이 있다. 이 때 for문과 while문 중 경우에 따라 사용해야하는 구문이 다르다.

1. for i in range(a, b, c) or for _ in range(n)과 같이 몇 번 반복해야하는지 횟수 또는 범위를 알 때는 for문을 사용
2. while True or while i < 100 or while a == 1 or while a와 같이 while 뒤에 조건이 붙고 언제 조건을 탈출해야할지 모를 때 while문 사용

• True로 len(bloom) = 10001로 채워져있는 bloom list를 만들고, 0번째와 1번째 index에 해당하는 값은 사용하지는 않지만 편의상 False로 채워넣는다. 1을 제외하고, 2부터 10000까지 for문으로 반복하고, bloom list의 index i의 값과 prime number를 판별하는 is_prime 함수에 i를 넣어 return되는 값이 모두 True일 경우에 j=2부터 시작하고, while문을 통해 j * i가 bloom list의 길이(10001)보다 작을때까지만 bloom list의 j * i번째 index 값을 False로 변경하며 반복된다. 10001 미만의 조건을 만족하는 2 ~ 10000까지 수의 배수에 해당하는 값을 bloom list의 index로 사용하여 해당 위치의 값을 False로 변경해주어 prime number는 True를 유지하게하고, 합성수를 False로 변경해주는 반복문이라고 생각하면 된다.

• input값을 T로 받고, T만큼 for문으로 반복해준다. 합성수 input을 n이라는 변수로 받고, 합성수 n에 대해 두 prime number의 합으로 출력을 해야하는데, 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 prime number의 차이가 가장 작은 것을 출력한다. 효율적인 코드를 위해 두 prime number의 차이가 가장 작은 것부터 출력해야하므로 n의 중간값을 mid로 설정해 for문으로 mid부터 2까지 1씩 감소하게 반복하여 bloom list의 index i의 값과 index n-i의 값이 모두 True, 즉, prime number라면 i와 n-i 값을 출력하도록 하고, for문을 종료시킨다.

---