Kiểm tra số Achilles trong Python

Số Achilles là số mạnh (powerful) 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 có p^2 cũng ước. Ví dụ: 72, 108, 200...

Ví dụ: 108 → True (6 và 36 đều chia hết, không phải bình phương hoàn hảo).

Thuật toán

check_powerful(n): phân tích thừa số nguyên tố, kiểm tra mỗi số mũ ≥ 2
check_power(a): kiểm tra a có phải x^y (y≥2) không
Số Achilles nếu powerful == True và power == False

Ví dụ mã Python

from math import sqrt, log
def check_powerful(n):
    while n % 2 == 0:
        p = 0
        while n % 2 == 0:
            n //= 2
            p += 1
        if p == 1:
            return False
    p = int(sqrt(n)) + 1
    for factor in range(3, p, 2):
        p = 0
        while n % factor == 0:
            n //= factor
            p += 1
        if p == 1:
            return False
    return n == 1

def check_power(a):
    if a == 1:
        return True
    p = int(sqrt(a)) + 1
    for i in range(2, a):
        val = log(a) / log(i)
        if (val - int(val)) < 1e-8:
            return True
    return False

def isAchilles(n):
    return check_powerful(n) and not check_power(n)

n = 108
print(isAchilles(n))

Đầu vào

Đầu ra

True