어떤 수 n이 주어졌을 때, 이 수가 팩토리얼 소수(Factorial Prime)인지 확인하는 방법을 알아보겠습니다. 팩토리얼 소수란 어떤 자연수의 팩토리얼(계승)에서 1을 뺀 값 또는 1을 더한 값이면서 동시에 소수인 수를 말합니다.
예를 들어 입력값이 n = 719라면 결과는 True가 됩니다. 그 이유는 719 = 720 − 1 = 6! − 1, 즉 719가 6의 팩토리얼보다 1 작은 소수이기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 먼저 num이 소수인지 확인하고, 소수가 아니라면 False를 반환합니다.
- factorial을 1로, i를 1로 초기화합니다.
- factorial이 num + 1 이하인 동안 반복합니다.
- factorial에 i를 곱합니다.
- num + 1이 factorial과 같거나 num − 1이 factorial과 같으면 True를 반환합니다.
- i를 1 증가시킵니다.
- 반복문이 끝날 때까지 조건을 만족하지 않으면 False를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
from math import sqrt
def isPrime(num) :
if num <= 1:
return False
if num <= 3 :
return True
if num % 2 == 0 or num % 3 == 0:
return False
for i in range(5, int(sqrt(num)) + 1, 6) :
if num % i == 0 or num % (i + 2) == 0:
return False
return True
def solve(num) :
if not isPrime(num) :
return False
factorial = 1
i = 1
while factorial <= num + 1:
factorial *= i
if num + 1 == factorial or num - 1 == factorial :
return True
i += 1
return False
num = 719
print(solve(num))입력
719
출력
True
참고: 대표적인 팩토리얼 소수
참고로 알려진 팩토리얼 소수에는 2(= 1! + 1), 3(= 2! + 1), 5(= 3! − 1), 7(= 3! + 1), 23(= 4! − 1), 719(= 6! − 1) 등이 있습니다. 팩토리얼 값이 매우 빠르게 커지기 때문에 위 알고리즘의 반복 횟수는 입력 크기에 비해 매우 적어 효율적으로 동작합니다.