TIL) 9020 골드바흐의 추측

🧵 에라토스의 체

소수를 구하는 가장 효율적인 방법이다.

💡 아이디어

• 숫자의 개수에 맞춰 미리 배열을 True/False로 초기화해놓고
• 2부터 시작해서 끝까지 2의 배수, 3의 배수, 4의 배수 ... 를 지워나감

eratos = [1] * 10001
eratos[0] = 0
eratos[1] = 0

for i in range(2, 10000):
    if eratos[i] == 1:
        j = 2 # j는 2부터 시작
        while i*j <= 10000:
            eratos[i*j] = 0
            j += 1

🧶 골드바흐의 추측

에라토스의 체를 이용해서 해결하는 문제이다.
숫자를 입력받은 후 에라토스의 체를 통해서 소수이면 조건을 만족해서 출력된다.

eratos = [1] * 10001
eratos[0] = 0
eratos[1] = 0

for i in range(2, 10000):
    if eratos[i] == 1:
        j = 2 # j는 2부터 시작
        while i*j <= 10000:
            eratos[i*j] = 0
            j += 1

# N을 입력받음
N = int(input())

for i in range(0, N):
    num = int(input())
    num1 = -1
    num2 = -1
    # 절반의 숫자만 반복
    for j in range(2, int(num//2)+1):
        if eratos[j] and eratos[num-j]:
            num1 = j
            num2 = num-j
    print(num1, num2)