숫자 n이 주어졌을 때, 이 수를 두 반소수(세미프라임, semi-prime)의 합으로 표현할 수 있는지 확인하는 문제를 함께 풀어보겠습니다.
반소수(Semi-prime)란 무엇인가?
반소수는 두 개의 소수를 곱하여 만들 수 있는 수를 의미합니다. 예를 들어 4 = 2 × 2, 6 = 2 × 3, 15 = 3 × 5처럼 소인수가 정확히 두 개인 수가 반소수에 해당합니다.
1부터 100 사이에 존재하는 반소수는 다음과 같습니다.
4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95
문제 이해하기
예를 들어 입력이 n = 108이라면 결과는 True입니다. 그 이유는 108 = 14 + 94로 표현할 수 있고, 14(= 2 × 7)와 94(= 2 × 47)는 각각 반소수이기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 탐색 범위를 MAX = 10000으로 설정합니다. 즉, 주어진 입력은 1부터 10000 범위 안의 반소수들의 합이라고 가정합니다.
- 발견된 반소수를 저장할 리스트(nums)와 각 수가 반소수인지 여부를 표시하는 불리언 배열(s_prime_flags)을 준비합니다.
- get_semi_primes() 함수에서 2부터 MAX-1까지의 모든 수에 대해 소인수 분해를 수행하여, 소인수가 정확히 2개인 수를 반소수로 표시하고 목록에 추가합니다.
- solve(n) 함수에서는 반소수 목록을 순회하면서 n에서 해당 반소수를 뺀 값(n - nums[i]) 역시 반소수인지 확인합니다. 대칭성 때문에 n ÷ 2까지만 검사하면 충분합니다.
- 조건을 만족하는 조합이 하나라도 있으면 True를, 끝까지 찾지 못하면 False를 반환합니다.
파이썬 구현 코드
MAX = 10000
nums = []
s_prime_flags = [False] * MAX
def get_semi_primes():
for i in range(2, MAX):
count = 0
num = i
j = 2
while count < 2 and j * j <= num:
while num % j == 0:
num //= j
count += 1
j += 1
if num > 1:
count += 1
if count == 2:
s_prime_flags[i] = True
nums.append(i)
def solve(n):
get_semi_primes()
i = 0
while nums[i] <= n // 2:
if s_prime_flags[n - nums[i]]:
return True
i += 1
return False
n = 108
print(solve(n))실행 결과
True
동작 원리 자세히 살펴보기
get_semi_primes() 함수는 각 수를 2부터 그 수의 제곱근까지 나누어 보면서 소인수의 개수를 셉니다. 나눗셈이 끝난 후에도 남은 값이 1보다 크다면 그 값 자체가 소수이므로 소인수 개수를 하나 더 증가시킵니다. 최종적으로 소인수 개수가 정확히 2라면 해당 수를 반소수로 기록합니다.
solve() 함수는 미리 계산된 반소수 목록을 활용하여, n보다 작거나 같은 각 반소수 p에 대해 n - p가 반소수인지 배열 조회만으로 빠르게 판별합니다. 이 덕분에 매번 소인수 분해를 반복하지 않아도 되므로 효율적입니다.
시간 복잡도
반소수를 미리 계산하는 과정은 각 수마다 제곱근까지 탐색하므로 O(MAX × √MAX)의 시간이 걸립니다. 이후 실제 답을 구하는 과정은 n/2 이하의 반소수 개수에 비례하며, 배열 조회는 상수 시간에 이루어집니다. 동일한 범위에서 여러 질의를 처리해야 하는 경우 사전 계산 방식이 특히 유리합니다.