어떤 자연수 n이 주어졌을 때, 이 숫자가 유클리드 수(Euclid Number)에 해당하는지 판별하는 문제를 살펴보겠습니다.
유클리드 수란?
유클리드 수는 다음과 같은 형태로 표현할 수 있는 정수를 말합니다.
n = Pn# + 1
여기서 Pn#은 처음 n개의 소수를 모두 곱한 값(소수 곱, 프리모리얼)을 의미합니다. 즉, 앞에서부터 소수를 차례대로 곱한 뒤 1을 더한 수가 바로 유클리드 수입니다.
예를 들어 입력값이 n = 211이라면 결과는 True입니다. 그 이유는 211을 다음과 같이 표현할 수 있기 때문입니다.
211 = (2 × 3 × 5 × 7) + 1
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 탐색 범위의 최댓값 MAX를 10000으로 설정합니다.
- 소수를 저장할 빈 리스트 primes를 준비합니다.
- generate_all_primes() 함수를 정의하여 에라토스테네스의 체 방식으로 범위 내의 모든 소수를 구합니다.
- prime 배열을 MAX 크기로 만들고 True로 초기화합니다.
- x = 2부터 시작해 x * x < MAX인 동안 반복하며, prime[x]가 True이면 x의 배수들을 모두 False로 표시합니다.
- 마지막으로 prime[x]가 True로 남아 있는 x를 primes 리스트에 추가합니다.
- 메인 로직에서는 mul = 1, i = 0으로 초기화한 뒤, mul이 n보다 작은 동안 다음을 반복합니다.
- mul에 소수를 하나씩 곱해 나갑니다.
- 곱한 값에 1을 더한 결과(mul + 1)가 n과 같으면 True를 반환합니다.
- 반복이 끝날 때까지 조건을 만족하지 못하면 False를 반환합니다.
예제 코드
MAX = 10000
primes = []
def generate_all_primes():
# 에라토스테네스의 체로 소수 생성
prime = [True] * MAX
x = 2
while x * x < MAX:
if prime[x] == True:
for i in range(x * 2, MAX, x):
prime[i] = False
x += 1
for x in range(2, MAX):
if prime[x]:
primes.append(x)
def solve(n):
generate_all_primes()
mul = 1
i = 0
while mul < n:
mul = mul * primes[i]
if mul + 1 == n:
return True
i += 1
return False
n = 211
print(solve(n))입력
211
출력
True
동작 원리 정리
이 알고리즘은 먼저 에라토스테네스의 체를 활용해 2부터 MAX까지의 모든 소수를 효율적으로 구합니다. 이후 소수를 2, 3, 5, 7, ... 순서대로 하나씩 곱해 가면서 각 시점의 누적 곱에 1을 더한 값이 목표 숫자 n과 일치하는지 확인합니다. 일치하는 지점이 발견되면 해당 숫자는 유클리드 수이므로 True를 반환하고, 끝까지 일치하지 않으면 False를 반환합니다.
참고로 유클리드 수의 예시로는 3, 7, 31, 211, 2311 등이 있으며, 고대 그리스 수학자 유클리드가 소수가 무한히 많다는 사실을 증명할 때 사용한 개념과 깊은 관련이 있습니다.