Kiểm tra số Trojan trong C++

Khái niệm

Cho số n, kiểm tra xem n có phải là số Trojan hay không. Số Trojan là số mạnh (strong number) nhưng không phải lũy thừa hoàn hảo. Số mạnh: mọi thừa số nguyên tố p của n đều có p² cũng chia hết n (tức là mỗi thừa số nguyên tố xuất hiện ít nhất 2 lần).

Tất cả số Trojan đều là số mạnh, nhưng ngược lại không đúng.

Ví dụ:

• n = 72 → YES. 72 = 6×6×2 = (6²)×2, mạnh nhưng không phải lũy thừa hoàn hảo.
• n = 16 → NO. 16 = 2⁴, mạnh nhưng là lũy thừa hoàn hảo.

Phương pháp

• Đếm số lần xuất hiện của mỗi thừa số nguyên tố. Nếu mọi thừa số đều xuất hiện ≥ 2 lần → số mạnh.
• Kiểm tra n có thể viết dưới dạng a^b (a,b > 1) hay không. Nếu không → không phải lũy thừa hoàn hảo.
• Kết luận: nếu mạnh VÀ không phải lũy thừa hoàn hảo → Trojan.

Ví dụ (C++)

// CPP program to check if a number is Trojan Number or not
#include <bits/stdc++.h>
using namespace std;

bool isPerfectPower1(int n1){
    if (n1 == 1) return true;
    for (int x1 = 2; x1 <= sqrt(n1); x1++) {
        int y1 = 2;
        int p1 = pow(x1, y1);
        while (p1 <= n1 && p1 > 0) {
            if (p1 == n1) return true;
            y1++;
            p1 = pow(x1, y1);
        }
    }
    return false;
}

bool isStrongNumber1(int n1){
    unordered_map<int, int> count1;
    while (n1 % 2 == 0) { n1 /= 2; count1[2]++; }
    for (int i1 = 3; i1 <= sqrt(n1); i1 += 2) {
        while (n1 % i1 == 0) { n1 /= i1; count1[i1]++; }
    }
    if (n1 > 2) count1[n1]++;
    for (auto b : count1) if (b.second == 1) return false;
    return true;
}

bool isTrojan1(int n1){
    return !isPerfectPower1(n1) && isStrongNumber1(n1);
}

int main(){
    int n1 = 72;
    if (isTrojan1(n1)) cout << "YES";
    else cout << "NO";
    return 0;
}

Đầu ra

Yes