C++로 숫자가 비정상 수(Unusual Number)인지 확인하는 방법

이번 글에서는 어떤 숫자가 비정상 수(Unusual Number)인지 판별하는 방법을 알아보겠습니다. 비정상 수란, 그 수의 가장 큰 소인수가 해당 수의 제곱근보다 엄격하게 큰 경우를 말합니다.

비정상 수의 예시는 다음과 같습니다: 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46

해결 접근 방식

이 문제를 해결하려면 먼저 주어진 수의 가장 큰 소인수를 구한 뒤, 그 값이 해당 수의 제곱근보다 큰지 확인하면 됩니다. 만약 가장 큰 소인수가 제곱근보다 크다면 그 수는 비정상 수이고, 그렇지 않다면 비정상 수가 아닙니다.

알고리즘 단계

1. 주어진 수에서 2로 나누어 떨어지는 부분을 모두 제거하며 최대 소인수를 갱신합니다.
2. 3부터 시작하여 홀수만 대상으로 √num까지 반복하며 나누어 떨어지는 인수들을 제거하고 최대 소인수를 기록합니다.
3. 위 과정 후 남은 값이 2보다 크다면 그 값 자체가 가장 큰 소인수입니다.
4. 구한 최대 소인수가 원래 수의 제곱근보다 큰지 비교하여 결과를 반환합니다.

예제 코드

#include <iostream>
#include <cmath>
using namespace std;

int largestPrimeFactor(int num) {
    int max_prime = -1;
    while (num % 2 == 0) { // 숫자에서 2를 모두 제거
        max_prime = 2;
        num >>= 1;
    }
    for (int i = 3; i <= sqrt(num); i += 2) {
        while (num % i == 0) {
            max_prime = i;
            num = num / i;
        }
    }
    if (num > 2)
        max_prime = num;
    return max_prime;
}

bool isUnusual(int num) {
    int largePrimeFactor = largestPrimeFactor(num);
    if (largePrimeFactor > sqrt(num)) {
        return true;
    } else {
        return false;
    }
}

int main() {
    int n = 14;
    if (isUnusual(n)) {
        cout << n << " is an unusual number";
    } else {
        cout << n << " is not an unusual number";
    }
}

실행 결과

14 is an unusual number

코드 설명

위 예제에서 n = 14인 경우를 살펴보겠습니다. 14의 소인수분해 결과는 2 × 7이므로 가장 큰 소인수는 7입니다. 14의 제곱근은 약 3.74이고, 7은 이보다 크기 때문에 14는 비정상 수로 판별됩니다.

반면, 예를 들어 12의 경우 소인수분해는 2 × 2 × 3으로 가장 큰 소인수가 3이고, 12의 제곱근(약 3.46)보다 작으므로 비정상 수가 아닙니다.

이 알고리즘의 시간 복잡도는 소인수분해 과정이 √n까지의 시행만 필요하므로 O(√n)입니다.