ตรวจสอบว่าเป็นเลขโทรจัน (Trojan Number) หรือไม่ใน C++

แนวคิด

เลขโทรจัน (Trojan Number) คือจำนวนที่เป็น Strong Number (ทุกเฉพาะตัวประกอบ p มี p² หารมันลงตัว ทุกเฉพาะตัวปรากฏอย่างน้อย 2 ครั้ง) แต่ ไม่ใช่ Perfect Power (ไม่สามารถเขียนในรูป a^b ได้เมื่อ a,b > 1)

หมายเหตุ: เลขโทรจันทุกตัวเป็น Strong Number แต่ไม่ใช่ทุก Strong Number เป็น Trojan Number

ตัวอย่าง: - 72 = 6×6×2 = (6²)×2 → Strong Number แต่ไม่ใช่ Perfect Power → YES - 16 = 2×2×2×2 = 2⁴ → Strong Number แต่เป็น Perfect Power → NO

วิธีการแก้ปัญหา

1. นับจำนวนของแต่ละเฉพาะตัวประกอบ ถ้าทุกตัวมีจำนวน ≥ 2 → เป็น Strong Number
2. ตรวจสอบว่าเป็น Perfect Power หรือไม่ (มี a^b = n, a,b > 1)
3. ถ้าเป็น Strong Number และไม่ใช่ Perfect Power → เป็น Trojan Number

ตัวอย่างโค้ด C++

#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;
}

ผลลัพธ์

Yes