백준 / 골드바흐의 추측 / 9020번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 골드바흐의 추측 / 9020번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/9020

 

문제 설명

---

나의 풀이

import math


# 소수를 찾는 함수
def prime_number(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n == 3:
        return True
    else:
        # 제곱 수의 이하로 나눴을 때 0이면 소수가 아니가.
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
    # 소수임
    return True


# 1. 2 ~ 10000까지의 숫자 중 소수의 배수가 되는 숫자를 모두 제거한다.
def euclid():
    prime = [False] * (10001) # 소수 배열을 만든다. 소수는 True, 논 소수면 False

    # 에라토스테네스의 체 초기화 (2부터 10000까지 True로 설정)
    for i in range(2, 10001):
        prime[i] = True

    # 체 적용
    for num in range(2, int(math.sqrt(10000)) + 1):
        if prime[num]:
            for multiple in range(num * num, 10001, num):
                prime[multiple] = False
    
    answer = [] # 정답

    t = int(input()) # 각 테스트 케이스

    for _ in range(t):
        n = int(input())

        num1, num2 = 0, 0
        
        # N/2부터 역순으로 탐색하여 두 소수를 찾는 로직
        for i in range(n // 2, 1, -1):
            if prime[i] and prime[n - i]:
                num1 = i
                num2 = n - i
                break
        
        if num1 != 0 and num2 != 0:
            answer.append((num1, num2))
    
    for i, j in answer:
        print(i, j)

        
euclid()

---

※ 알아야 할 것

1. 유클리드 호제법 이용해서 모든 소수가 아닌 수를 찾는다.

2. 소수만 모아둔 배열을 이용해서 역순으로 찾아서 투 포인트 기법으로 가장 작은 값을 찾는다.

3. 찾으면 배열에 넣어 저장하고 종료한다.