丑数

题目：我们把只包含因子

2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。

所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3和5整除。也就是说如果一个数如果它能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以连续5。如果最后我们得到的是1，那么这个数就是丑数，否则不是。

基于前面的分析，我们可以写出如下的函数来判断一个数是不是丑数：

#include <iostream>using namespace std;int ugly[5900];void getuglynum(){    ugly[0]=1;    int i = 1;    int t1=0,t2=0,t3=0,t4=0;    while(i<=5841)    {        while(ugly[t1]*2<=ugly[i-1])            t1++;        while(ugly[t2]*3<=ugly[i-1])            t2++;        while(ugly[t3]*5<=ugly[i-1])            t3++;        while(ugly[t4]*7<=ugly[i-1])            t4++;        ugly[i++] = min(min(ugly[t1]*2,ugly[t2]*3),min(ugly[t3]*5,ugly[t4]*7));    }}int main(){    int n;    getuglynum();    while(cin>>n&&n)    {        cout<<"The "<<n;        if(n%10==1&&n%100!=11)            cout<<"st";         else if(n%10==2&&n%100!=12)         cout<<"nd";         else if(n%10==3&&n%100!=13)          cout<<"rd";        else            cout<<"th";        cout<<" humble number is "<<ugly[n-1]<<"."<<endl;    }    return 0;}