[ 2023-03-11 🧙‍♂️ TIL ]

백준 9020번

콜드바흐의 추측
모든 짝수는 두 소수의 합으로 나타낼 수 있다는 추측입니다.

이 문제는 해당 추측이 맞는지 확인하는 코드를 구현하는 문제입니다.

처음에 문제를 풀었을 때 계속 시간초과가 발생하여 해결하지 못하였습니다.
(아래는 시간 초과가 발생하는 코드)

import sys

input = sys.stdin.readline

primes = {}

def isPrime(val):
    count = 0
    num = 2

    while num * num <= val:
        if (val % num) == 0:
            count += 1
        num += 1

    if count == 0:
        return True
    else:
        return False

t = int(input())
input_arr = []
primes = {}
max_val = 0

for val in range(2, 10000):
    if isPrime(val):
        primes[val] = val

sosu = primes.keys()

for _ in range(t):
    check = True
    n = int(input())
    a = 0
    b = val
    for num1 in sosu:
        if num1 > (n // 2):
            break
        if num1 in primes:
            for num2 in sosu:
                if (num2 in primes) and (num1 + num2 == n):
                    if abs(num1 - num2) < abs(a-b):
                        a = num1
                        b = num2
    print(a, b)

미리 제공되는 수까지의 범위의 소수가 들어있는 딕셔너리를 만들고 이를 이용하여 해결하는 풀이였습니다.

하지만 시간초과의 문제가 생겼고 이를 해결하기 위해 결국 구글링하여 해결하였습니다.

(아래는 시간초과문제를 해결한 코드)

import sys


def isPrime(val):
    count = 0
    num = 2

    while num * num <= val:
        if (val % num) == 0:
            count += 1
        num += 1

    if count == 0:
        return True
    else:
        return False


input = sys.stdin.readline

n = int(input())

for _ in range(n):
    num = int(input())
    half = left = num//2 # 입력으로 들어온 수의 반으로 나눔

    for right in range(half, num): 
    # 중간부터 끝까지 반복문을 돌면 두 수차가 제일 작은 수부터 소수를 찾기시작한다.
        if isPrime(left) and isPrime(right):
            print(left, right)
            break
        left -= 1