丑数
丑数是素数为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;
//查找下一个倍数为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