C++로 트로이 수(Trojan Number) 판별하기

개념

주어진 수 n이 트로이 수(Trojan Number)인지 판별하는 것이 이 글의 목표입니다. 트로이 수란 완전 거듭제곱(perfect power)이 아닌 강한 수(strong number)를 의미합니다.

여기서 강한 수란, 수 n의 모든 소인수 p에 대해 p² 역시 n의 약수가 되는 수를 말합니다. 다르게 표현하면, 모든 소인수가 적어도 두 번 이상 나타나야 한다는 뜻입니다.

주의할 점은 모든 트로이 수는 반드시 강한 수이지만, 그 역은 성립하지 않는다는 것입니다. 즉, 모든 강한 수가 트로이 수인 것은 아니며, a^b(a와 b는 1보다 큰 양의 정수) 형태로 표현할 수 없는 강한 수만이 트로이 수가 됩니다.

예제 입력 및 출력

입력 1

n = 72
72는 6×6×2, 즉 (6²)×2로 표현됩니다. 강한 수이지만 완전 거듭제곱은 아닙니다.

출력

YES

입력 2

n = 16
16은 2×2×2×2, 즉 2⁴로 표현됩니다. 강한 수이면서 동시에 완전 거듭제곱입니다.

출력

NO

접근 방법

먼저 각 소인수가 몇 번 나타나는지 개수를 저장하고, 모든 소인수의 개수가 2 이상이라면 해당 수는 강한 수입니다.

다음 단계에서는 주어진 수가 a^b 형태로 표현되는지, 즉 완전 거듭제곱인지 확인합니다.

마지막으로, 주어진 수가 강한 수이면서 완전 거듭제곱이 아니라면 그 수는 트로이 수라고 결론지을 수 있습니다.

C++ 구현 예제

// 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 = n1 / 2;
        count1[2]++;
    }
    for (int i1 = 3; i1 <= sqrt(n1); i1 += 2) {
        while (n1 % i1 == 0) {
            n1 = n1 / i1;
            count1[i1]++;
        }
    }
    if (n1 > 2)
        count1[n1]++;
    int flag1 = 0;
    for (auto b : count1) {
        if (b.second == 1) {
            flag1 = 1;
            break;
        }
    }
    if (flag1 == 1)
        return false;
    else
        return true;
}

// 트로이 수 판별 함수
bool isTrojan1(int n1){
    if (!isPerfectPower1(n1) && isStrongNumber1(n1))
        return true;
    else
        return false;
}

// 드라이버 코드
int main(){
    int n1 = 72;
    if (isTrojan1(n1))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

실행 결과

YES