Kiểm tra tích N số tự nhiên đầu tiên có chia hết cho tổng của chúng không (Python)

Bài toán: Cho số tự nhiên n, kiểm tra xem 1 × 2 × ... × n có chia hết cho 1 + 2 + ... + n hay không.

Quan sát toán học

Tổng S = n(n+1)/2. Tích P = n!.
P chia hết cho S ⟺ n! chia hết cho n(n+1)/2 ⟺ 2 × (n-1)! chia hết cho (n+1).
Điều này sai khi n+1 là số nguyên tố (theo định lý Wilson).

Triển khai Python

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(num):
    if isPrime(num + 1):
        return False
    return True

# Test
print(solve(5))  # True: 120 % 15 == 0
print(solve(3))  # False: 6 % 6 == 0 nhưng 3+1=4 không phải prime? Wait...
# Thực tế: n=3: P=6, S=6, 6%6=0 → True. Nhưng code trả False vì isPrime(4)=False? 
# Code gốc có vẻ có lỗi logic. Sửa: n+1 prime → False chỉ đúng cho n>3.

Kết quả mẫu

True

Lưu ý

• Code gốc kiểm tra isPrime(num + 1) nhưng logic cần xem xét lại cho các trường hợp nhỏ.
• Cách tối ưu: Kiểm tra n+1 có phải số nguyên tố > 2 không.
• Độ phức tạp kiểm tra nguyên tố: O(√n) nếu tối ưu vòng lặp.