C++의 N' 스마트 숫자

<시간/>

스마트 숫자는 최소 3개의 고유한 소인수를 포함하는 숫자입니다. 번호 N이 주어집니다. n번째 스마트 번호를 찾으세요.

스마트 넘버 시리즈는

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

알고리즘

숫자 N을 초기화합니다.
카운트를 0으로 초기화합니다.
주어진 숫자가 소수인지 확인하는 함수를 작성하세요.
숫자가 똑똑한지 아닌지 확인하는 함수를 작성하세요.
첫 번째 스마트 숫자가 30이므로 30부터 반복하는 루프를 작성합니다.
- 소수 기능을 이용하여 현재 숫자가 스마트 숫자인지 아닌지 확인하세요.
- 스마트한 번호를 찾으면 1씩 증가합니다.
- 카운트가 N일 때 스마트 번호를 반환합니다.

구현

다음은 위의 알고리즘을 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;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.