C++로 N번째 스마트 넘버(Smart Number) 구하기

스마트 넘버(Smart Number)란?

스마트 넘버는 서로 다른 소인수(prime factor)를 최소 3개 이상 가진 수를 의미합니다. 예를 들어 30은 2 × 3 × 5로 표현되므로 세 개의 서로 다른 소인수를 가지며, 스마트 넘버에 해당합니다.

숫자 N이 주어졌을 때 N번째 스마트 넘버를 찾는 것이 이 문제의 목표입니다. 스마트 넘버 수열은 다음과 같습니다.

30, 42, 60, 66, 70, 78 ...

30 = 2 × 3 × 5
42 = 2 × 3 × 7
60 = 2² × 3 × 5 (중복된 소인수는 하나로 계산)

알고리즘 접근 방법

찾으려는 순서 N을 초기화합니다.
발견한 스마트 넘버의 개수를 세는 카운트를 0으로 초기화합니다.
주어진 수가 소수인지 판별하는 함수를 작성합니다.
주어진 수가 스마트 넘버인지 확인하는 함수를 작성합니다.
첫 번째 스마트 넘버가 30이므로 30부터 시작하는 반복문을 작성합니다.
- 소수 판별 함수를 활용해 현재 수가 스마트 넘버인지 검사합니다.
- 스마트 넘버를 발견할 때마다 카운트를 1씩 증가시킵니다.
- 카운트가 N과 같아지면 해당 수를 반환합니다.

C++ 구현 코드

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include<bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

bool isSmartNumber(int n) {
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (n % i == 0 && isPrime(i)) {
            count += 1;
        }
        if (count == 3) {
            return true;
        }
    }
    return false;
}

int getNthSmartNumber(int n) {
    int i = 30, count = 0;
    while (true) {
        if (isSmartNumber(i)) {
            count += 1;
        }
        if (count == n) {
            return i;
        }
        i += 1;
    }
}

int main() {
    int N = 25;
    cout << getNthSmartNumber(N) << endl;
    return 0;
}

코드 설명

isPrime(int n) : 2부터 √n까지의 수로 나누어 보아 나누어떨어지는 수가 없으면 소수로 판별합니다.
isSmartNumber(int n) : n의 약수 중 소수의 개수를 세고, 3개 이상이면 true를 반환합니다.
getNthSmartNumber(int n) : 30부터 한 수씩 검사하며 n번째 스마트 넘버를 찾아 반환합니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다. N = 25일 때 25번째 스마트 넘버인 174가 화면에 나타납니다.

성능 개선 팁

현재 구현은 각 수마다 모든 약수를 검사하므로 수가 커질수록 실행 시간이 길어집니다. 소인수를 찾을 때 해당 소수로 n을 계속 나누어 중복 검사를 제거하거나, 에라토스테네스의 체로 미리 소수 목록을 만들어 두면 실행 속도를 크게 개선할 수 있습니다.