Python에서 소수를 두 소수의 합으로 표현할 수 있는지 확인하는 방법

문제 개요

소수 n이 하나 주어졌을 때, 이 숫자를 두 소수 x와 y의 합(x + y) 형태로 표현할 수 있는지 확인하는 것이 목표입니다.

예를 들어 n = 19라면, 19 = 17 + 2처럼 두 소수의 합으로 나타낼 수 있으므로 결과는 True가 됩니다.

핵심 아이디어

n 자체가 소수이면서 2보다 크다면 n은 항상 홀수입니다. 그런데 홀수는 '짝수 + 홀수'의 조합으로만 만들 수 있기 때문에, 두 소수의 합이 되려면 둘 중 하나가 반드시 유일한 짝수 소수인 2여야 합니다.

따라서 모든 경우를 탐색할 필요 없이, n − 2가 소수인지만 확인하면 문제를 효율적으로 해결할 수 있습니다.

알고리즘 단계

먼저 소수 판별 함수 isPrime()을 정의합니다.

• number ≤ 1이면 False를 반환합니다.
• number가 2이면 True를 반환합니다.
• number가 짝수이면 False를 반환합니다.
• 3부터 √number의 정수 부분 + 1까지 2씩 증가시키며 반복하고, number가 i로 나누어떨어지면 False를 반환합니다.
• 위 조건에 해당하지 않으면 True를 반환합니다.

메인 로직에서는 다음과 같이 처리합니다.

• isPrime(number)와 isPrime(number - 2)가 모두 참이면 True를 반환합니다.
• 그렇지 않으면 False를 반환합니다.

구현 예제

from math import sqrt

def isPrime(number):
    if number <= 1:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    for i in range(3, int(sqrt(number)) + 1, 2):
        if number % i == 0:
            return False
    return True

def solve(number):
    if isPrime(number) and isPrime(number - 2):
        return True
    else:
        return False

n = 19
print(solve(n))

입력

19

출력

True

복잡도 분석

소수 판별 함수는 3부터 √n까지 홀수만 검사하므로 시간 복잡도는 O(√n)입니다. 전체 풀이에서 소수 판별을 두 번만 수행하므로 전체 시간 복잡도 역시 O(√n)이며, 추가 메모리는 사용하지 않아 공간 복잡도는 O(1)입니다.

마무리

이 문제는 골드바흐 추측(Goldbach's Conjecture)과 관련된 개념으로, '짝수는 두 소수의 합으로 표현된다'는 유명한 가설과 맞닿아 있습니다. 특히 소수 n이 홀수라는 성질을 활용하면 탐색 범위를 크게 줄일 수 있어, 단순한 완전 탐색보다 훨씬 효율적인 코드를 작성할 수 있다는 점이 핵심 포인트입니다.