BAEKJOON PYTHON 9020 골드바흐의 추측

Prob

---

Approach

제한조건에 맞게 10000까지의 소수를 모두 구한다.

입력한 숫자의 절반부터 1씩 줄이며 소수인지 확인한다.

반대 숫자도 소수인지 확인한다.

---

Code

if __name__ == "__main__" :
    
    is_prime = [False, False] + [True] * ((10000) - 1)
    primes = []
    for i in range(2, 10000 + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, 10000 + 1, i):
                is_prime[j] = False
    
    T = int(input())
    for i in range(T):
        num = int(input())
        for j in range(int(num / 2), 0, -1):
            if j in primes:
                if (num - j) in primes:
                    print("%d %d"%(j, num - j))
                    break

 

출처

https://www.acmicpc.net/problem/9020