어떤 수 n이 주어졌을 때, 이 수가 프라이모리얼 소수(Primorial Prime)인지 판별해야 합니다. 프라이모리얼 소수란 pN# + 1 또는 pN# − 1 형태를 가지는 소수를 말합니다. 여기서 pN#은 '프라이모리얼(primorial)'을 의미하며, 처음 N개의 소수들을 모두 곱한 값입니다.
예를 들어 입력값이 29라면 결과는 True가 됩니다. N=3일 때 프라이모리얼은 2 × 3 × 5 = 30이고, 30 − 1 = 29이므로 29는 pN# − 1 형태의 프라이모리얼 소수에 해당하기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- MAX := 100000으로 설정합니다.
- prime := 크기가 MAX인 리스트를 만들고 모든 값을 True로 초기화합니다.
- arr := 새로운 빈 리스트를 생성합니다.
- 에라토스테네스의 체(SieveOfEratosthenes) 함수를 정의합니다.
- pri를 2부터 int(sqrt(MAX)) + 1까지 반복하면서, prime[pri]가 True이면 pri*2부터 MAX까지 pri 간격으로 i를 증가시키며 prime[i]를 False로 설정합니다.
- 이후 pri를 2부터 MAX까지 순회하며 prime[pri]가 참인 값들을 arr 리스트에 추가합니다.
- 메인 로직에서는 다음을 수행합니다.
- n이 소수가 아니면(즉, prime[n]이 False이면) False를 반환합니다.
- product := 1, i := 0으로 초기화합니다.
- product가 n보다 작은 동안 product에 arr[i]를 곱하고, product + 1 == n 또는 product − 1 == n이면 True를 반환합니다.
- 조건을 만족하지 않으면 False를 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
from math import sqrt
MAX = 100000
prime = [True] * MAX
arr = []
def SieveOfEratosthenes() :
for pri in range(2, int(sqrt(MAX)) + 1) :
if prime[pri] == True :
for i in range(pri * 2 , MAX, pri) :
prime[i] = False
for pri in range(2, MAX) :
if prime[pri] :
arr.append(pri)
def check_primorial_prime(n) :
if not prime[n] :
return False
product, i = 1, 0
while product < n :
product *= arr[i]
if product + 1 == n or product - 1 == n :
return True
i += 1
return False
SieveOfEratosthenes()
n = 29
print(check_primorial_prime(n))입력
29
출력
True
정리
이 알고리즘은 에라토스테네스의 체를 사용해 미리 소수 목록을 구성한 뒤, 주어진 수가 소수인지 먼저 확인하고, 누적 곱(프라이모리얼)이 해당 수와 ±1 차이가 나는지 검사하는 방식으로 동작합니다. 시간 복잡도는 체 전처리에 O(MAX log log MAX), 판별 과정에는 소수 개수에 비례하는 선형 시간이 소요되므로 효율적으로 프라이모리얼 소수를 판별할 수 있습니다.