Kiểm tra số Achilles trong C++

Khái niệm

Cho số nguyên dương n, kiểm tra xem n có phải là số Achilles hay không. In "YES" nếu có, ngược lại "NO".

Số Achilles: Là số mạnh (powerful number) nhưng không phải lũy thừa hoàn hảo. Số mạnh: với mọi thừa số nguyên tố p của n, p² cũng chia hết n.

Các số Achilles đầu tiên: 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125.

Ví dụ:

• 108 → YES. 108 mạnh (chia hết cho 2² và 3²) nhưng không phải lũy thừa hoàn hảo.
• 64 → NO. 64 mạnh nhưng là 2⁶ (lũy thừa hoàn hảo).

Phương pháp

• Kiểm tra n có phải số mạnh: phân tích thừa số nguyên tố, mọi thừa số phải có lũy thừa ≥ 2.
• Kiểm tra n có phải lũy thừa hoàn hảo: tồn tại a, b > 1 sao cho n = a^b.
• Nếu mạnh VÀ không phải lũy thừa hoàn hảo → Achilles.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;

bool isPowerful1(int n1){
    while (n1 % 2 == 0) {
        int power1 = 0;
        while (n1 % 2 == 0) { n1 /= 2; power1++; }
        if (power1 == 1) return false;
    }
    for (int factor1 = 3; factor1 <= sqrt(n1); factor1 += 2) {
        int power1 = 0;
        while (n1 % factor1 == 0) { n1 /= factor1; power1++; }
        if (power1 == 1) return false;
    }
    return (n1 == 1);
}

bool isPower1(int a1){
    if (a1 == 1) return true;
    for (int i1 = 2; i1 * i1 <= a1; i1++) {
        double val1 = log(a1) / log(i1);
        if ((val1 - (int)val1) < 0.00000001) return true;
    }
    return false;
}

bool isAchillesNumber1(int n1){
    return isPowerful1(n1) && !isPower1(n1);
}

int main(){
    int n1 = 108;
    if (isAchillesNumber1(n1)) cout << "YES" << endl;
    else cout << "NO" << endl;
    n1 = 35;
    if (isAchillesNumber1(n1)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Đầu ra

YES NO