丑数
题目:我们把只包含因子
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;}