Kiểm tra số Troy (Trojan Number) trong Python

Số Troy là số mạnh (strong) nhưng không phải lũy thừa hoàn hảo. Số mạnh: mọi ước nguyên tố p đều xuất hiện ít nhất 2 lần (p^2 chia hết).

Ví dụ: 72 → True (72 = 6^2 × 2, số mạnh nhưng không phải lũy thừa).

Thuật toán

check_perfect_pow(n): kiểm tra n = x^y (y≥2)
check_strong_num(n): đếm tần suất ước nguyên tố, tất cả ≥ 2
Số Troy nếu not perfect_pow và strong_num

Ví dụ mã Python

from math import sqrt, pow
def check_perfect_pow(n):
    if n == 1:
        return True
    for x in range(2, int(sqrt(n)) + 1):
        y = 2
        p = x**y
        while p <= n and p > 0:
            if p == n:
                return True
            y += 1
            p = x**y
    return False

def check_strong_num(n):
    count = {i:0 for i in range(n)}
    while n % 2 == 0:
        n //= 2
        count[2] += 1
    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            n //= i
            count[i] += 1
    if n > 2:
        count[n] += 1
    for v in count.values():
        if v == 1:
            return False
    return True

def isTrojan(n):
    return not check_perfect_pow(n) and check_strong_num(n)

n = 72
print(isTrojan(n))

Đầu vào

Đầu ra

True