Kiểm tra số nguyên tố giai thừa (Factorial Prime) trong Python

Bài toán: Factorial Prime là số nguyên tố p sao cho p = k! ± 1 với một số nguyên k nào đó.

Ví dụ

719 = 720 - 1 = 6! - 1 → Factorial Prime.
Các factorial prime nhỏ: 2 (1!+1), 3 (2!+1), 5 (3!-1), 7 (3!+1), 23 (4!-1), 719 (6!-1), 5039 (7!-1)...

Triển khai Python

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

# Test
print(solve(719))   # True: 6! - 1
print(solve(7))     # True: 3! + 1
print(solve(11))    # False

Kết quả

True

Giải thích

• Kiểm tra nguyên tố tối ưu O(√n) bằng kiểm tra 6k±1.
• Tính giai thừa lũy tiến factorial *= i cho đến khi vượt quá num + 1.
• Kiểm tra num ± 1 == factorial tại mỗi bước.
• Độ phức tạp: O(√n + k) với k ~ log(num) (vì giai thừa tăng rất nhanh).