बदसूरत संख्या

बदसूरत संख्याएं वे संख्याएं हैं जिनके अभाज्य गुणनखंड 2, 3 या 5 हैं। 1 से 15 तक, 11 कुरूप संख्याएं हैं 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. संख्याएँ 7, 11, 13 कुरूप नहीं हैं क्योंकि वे अभाज्य हैं। 14 नंबर बदसूरत नहीं है क्योंकि इसके अभाज्य गुणनखंड में 7 आएगा।

इस प्रोग्राम में, हम nth बदसूरत नंबर खोजने की कोशिश करेंगे।

इनपुट और आउटपुट

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

एल्गोरिदम

getUglyNumbers(n)

इनपुट: शर्तों की संख्या।

आउटपुट: nth अग्ली नंबर खोजें।

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