Algorithm/BaekJoon

백준 21.12.10 9020번 - 골드바흐의 추측

HappyFrog 2021. 12. 10. 18:16

def IsPrime(n):
    seive = [True] * n

    for i in range(2, int((n ** 0.5) + 1)):
        if seive[i] == True:
            for j in range(i + i, n, i):
                seive[j] = False

    return [i for i in range(2, n) if seive[i] == True]

        
primeNumbers = IsPrime(10000)

T = int(input())

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

    for i in range(int(n/2), 1, -1):
        if primeNumbers.count(i) != 0:
            if primeNumbers.count(n - i) != 0:
                print(i, n - i)
                break
  • 아리스토테네스의 체 함수를 그대로 사용하여 문제에서 주어진 범위만큼의 리스트를 미리 생성했습니다.
  • 그 다음엔 주어진 n은 짝수이며 두 소수간의 차이가 가장 작은 값을 출력해야 하므로 2로 나누어 중간부터 1씩 줄여가며 값을 구하도록 반복문을 작성했습니다.
  • 만약 i가 리스트에 존재하는 소수라면 (n - i) 의 값 또한 소수인지 판별하여 출력하도록 했습니다.