못생긴 숫자

못생긴 숫자는 소인수가 2, 3 또는 5인 숫자입니다. 1부터 15까지 11개의 못생긴 숫자 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. 7, 11, 13은 소수이기 때문에 못생긴 것이 아닙니다. 숫자 14는 소인수에 7이 올 것이기 때문에 못생긴 것이 아닙니다.

이 프로그램에서 우리는 n번째 못생긴 숫자를 찾으려고 노력할 것입니다.

입력 및 출력

Input:
Take the term number. Say it is 10
Output:
The 10th ugly number is 12

알고리즘

getUglyNumbers(n)

입력: 용어의 수입니다.

출력: n번째 못생긴 숫자를 찾습니다.

Begin
   define array named uglyNum of size n
   i2 := 0, i3 := 0, i5 := 0
   next2mul := 2, next3mul := 3, next5Mul := 5
   next := 1
   ugluNum[0] := 1

   for i := 1 to n, do
      next := minimum of next2Mul, next3Mul and next5Mul
      uglyNum[i] := next
      if next = next2Mul, then
         i2 := i2 + 1
         next2mul := uglyNum[i2] * 2
      if next = next3Mul, then
         i3 := i3 + 1
         next3mul := uglyNum[i3] * 3
      if next = next5Mul, then
         i5 := i5 + 1
         next5mul := uglyNum[i5] * 5
   done
   return next
End

예시

# include<iostream>
using namespace std;

int min(int x, int y, int z) {            //find smallest among three numbers
   if(x < y) {
      if(x < z)
         return x;
      else
         return z;
   }else {
      if(y < z)
         return y;
      else
         return z;
   }
}

int getUglyNum(int n) {
   int uglyNum[n];          // To store ugly numbers
   int i2 = 0, i3 = 0, i5 = 0;

   //find next multiple as 1*2, 1*3, 1*5

   int next2mul = 2;
   int next3mul = 3;
   int next5mul = 5;
   int next = 1;              //initially the ugly number is 1

   uglyNum[0] = 1;

   for (int i=1; i<n; i++) {
      next = min(next2mul, next3mul, next5mul);       //find next ugly number
      uglyNum[i] = next;

      if (next == next2mul) {
         i2++;             //increase iterator of ugly numbers whose factor is 2
         next2mul = uglyNum[i2]*2;
      }

      if (next == next3mul) {
         i3++;             //increase iterator of ugly numbers whose factor is 3
         next3mul = uglyNum[i3]*3;
      }

      if (next == next5mul) {
         i5++;              //increase iterator of ugly numbers whose factor is 5
         next5mul = uglyNum[i5]*5;
      }
   }
   return next;        //the nth ugly number
}

int main() {
   int n;
   cout << "Enter term: "; cin >> n;
   cout << n << "th Ugly number is: " << getUglyNum(n) << endl;
}

출력

Enter term: 10
10th Ugly number is: 12