ตรวจสอบว่าเป็นจำนวนอัคคิลลีส (Achilles Number) หรือไม่ใน C++

แนวคิด

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

จำนวนอัคคิลลีสแรกๆ: 72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125

ตัวอย่าง: - 108 → YES (Powerful เพราะ 2² และ 3² หาร 108 ลงตัว แต่ไม่ใช่ Perfect Power) - 64 → NO (Powerful แต่เป็น Perfect Power เพราะ 64 = 2⁶ = 4³ = 8²)

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

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

ตัวอย่างโค้ด 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;
}

ผลลัพธ์

YES NO