অসুন্দর সংখ্যা (Ugly numbers) হলো এমন সংখ্যা যাদের প্রাইম ফ্যাক্টর শুধু ২, ৩ বা ৫। ১ থেকে ১৫ পর্যন্ত ১১টি অসুন্দর সংখ্যা রয়েছে: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15। ৭, ১১, ১৩ অসুন্দর নয় কারণ এগুলো প্রাইম। ১৪ অসুন্দর নয় কারণ এর প্রাইম ফ্যাক্টরে ৭ আসবে। ধরুন আমরা ১০ম অসুন্দর সংখ্যা বের করতে চাই। মানটি হবে ১২।
নিচের অ্যালগরিদমটি দেখে একটি ধারণা পাওয়া যাবে −
অ্যালগরিদম
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
উদাহরণ (C++)
# include<iostream> using namespace std; int min(int x, int y, int z){ //তিনটি সংখ্যার মধ্যে ছোটটি বের করা if(x < y){ if(x < z) return x; else return z; } else{ if(y < z) return y; return z; } } int getUglyNum(int n){ int uglyNum[n]; // অসুন্দর সংখ্যা সংরক্ষণের জন্য int i2 = 0, i3 = 0, i5 = 0; //পরবর্তী গুণফল বের করা 1*2, 1*3, 1*5 int next2mul = 2; int next3mul = 3; int next5mul = 5; int next = 1; //প্রাথমিক অসুন্দর সংখ্যা ১ uglyNum[0] = 1; for (int i=1; i<n; i++){ next = min(next2mul, next3mul, next5mul); //পরবর্তী অসুন্দর সংখ্যা বের করা uglyNum[i] = next; if (next == next2mul){ i2++; //যে অসুন্দর সংখ্যার ফ্যাক্টর ২ তার ইটারেটর বাড়ানো next2mul = uglyNum[i2]*2; } if (next == next3mul){ i3++; //যে অসুন্দর সংখ্যার ফ্যাক্টর ৩ তার ইটারেটর বাড়ানো next3mul = uglyNum[i3]*3; } if (next == next5mul){ i5++; //যে অসুন্দর সংখ্যার ফ্যাক্টর ৫ তার ইটারেটর বাড়ানো next5mul = uglyNum[i5]*5; } } return next; //n-তম অসুন্দর সংখ্যা } int main(){ int n; cout << "Enter term: "; cin >> n; cout << n << "th Ugly number is: " << getUglyNum(n)<< endl; }ইনপুট
10
আউটপুট
Enter term: 10 10th Ugly number is: 12
