什么是丑数：一个数的因子只包含2、3、5的数称为丑数。 由于数字1将特殊处理也视为丑数，因此从1开始的10个丑数分别为1、2、3、4、5、6、8、9、10、12。
当因子的概念：整数m除以n以获得剩余的商品时，n被称为m的一个因子。 例如8的因子是1、2、4、8。 丑陋数所要求的因子只含有2、3、5。 所以丑数中的因子应该理解为质因子。 也就是说，因子为素数，素数也称为素数，是指大于1的自然数，不能被1和除此以外的自然数整除的数。 与素数对应的数称为合数。
现在要求写一个输出从1到第n个丑数的程序。 就像第一个丑数是一，第二个丑数是二，第十个丑数是十二一样
判断是否是丑数的算法:作为判定对象的整数位m。 m循环除以2直到不能整除，此时再除以3，再除以5直到商为1或不能整除。 如果商为1，馀数为0，则为丑数，否则为非丑数。
例如丑数12
12之二=6
6/2=3；
3/2不能被整除
3/3=1； 结束了，12是个丑陋的数
非丑数26
26之二=13
13/2不能被整除
13/3不能被整除
13/5不能被整除
结束时，26不是整数
33558www.Sina.com/(1)设置计数出现的丑陋数的计数器
)2)从1开始遍历各整数，判断是否为丑数，若为丑数，则向计数器加1，否则遍历下一个整数。
)3)计数器的值=N时，停止遍历，输出丑数。
# include stdio.h # include time.h # include string.hintisugly (int number ) )确定number是否为丑数while (number %2===0) (while ) number%5==0) ) /判定数是否能被5整除number=number/5； (if ) number==1)//return 1； elsereturn 0； (intfindugly(intn ) )寻找从/1开始的第n个丑数的int count=0； int number=1为了计数//1到while(1) (if ) isugly ) number ) ) number向丑数计数器加1count时； (if ) count==n )//找出第n个丑数，返回丑数return number； elsenumber }}void main () {int N=0； scanf('%d '，n )； clock_t start=clock (； printf('%dn '，findUgly(N ) )； clock_t stop=clock (； printf(':%lf(n )，) stop - start )/CLOCKS_PER_SEC )； () ) ) ) )。
上面的算法从1开始扫描，寻找第n个丑数。 n较大时，需要时间。 n为1400时消耗23秒，随着n的变大，需要相当长的时间
寻找丑数算法1：考虑根据之前的丑数推测下一个丑数的方法。 不需要从1开始遍历进行判断。 从1开始的十个丑数分别是1、2、3、4、5、6、8、9、10、12。 可知1以外的丑数可从某些丑数*2或*3或*5获得。 例如，2是用丑数1*2得到的，3是用丑数1*3得到的，4是用丑数1*4得到的，5是用丑数1*5得到的，6是用丑数2*3得到的……
具体算法步骤：
)1)根据第一个丑数1，求出1 *2=2，1 *3=3，1 *5=5。
)2)以上乘积中取大于1的最小值的2，作为第2个丑数)由于丑数是增量序列，所以i 1个丑数一定大于I个丑数) )。
(3)求至丑数2的丑数与2、3、5之积)1*2=2，1 *3=3，1 *5=5； 2*2=4； 2*3=6； 2*5=10；
)4)在上的乘积中取大于2的最小值3，作为第3个丑数
……
……
(I )取出丑数I前的丑数与分别为2、3、5的乘积
(i 1 )将乘积中大于I的最小值作为丑数
(i 2 )重复I ) ) i 1 )的步骤，直到计数器等于n
# include stdio.h # include time.h # include string.h # define maxlen 99999//3用于求取个数的最小值intcompare(intchentwo，int chet cheched }elseif(chenthree=chenfive ) return chenThree； elsereturn chenFive； (//n第个丑数intfindugly(intn ) ) {int ugly[MaxLen]={1}； //在用于保存丑数的数组中，将丑数1存储在数组中的int count=1 //数组中只有丑数1，所以计数器为1while(1) {int chenTwo=0； int chenThree=0； int chenFive=0； /*ugly阵列中的最新丑数之一是ugly[count-1]，将ugly[count-1]之前的丑数乘以2，求出第一个乘积大于ugly[count-1]的值并保存在chenTwo中*/i count； I () if ) ugly[I]*2ugly[count-1] ) {chenTwo=ugly[i]*2； 黑； }}/*ugly数组的最新丑数之一是ugly[count-1]，将ugly[count-1]之前的丑数乘以3，求出第一个积大于ugly[count-1]的值并保存在chenThree中I ) if(ugly[I]*3ugly[count-1] ) {chenThree=ugly[i]*3； 黑； }}/*ugly数组中最新的丑数之一是ugly[count-1]，将ugly[count-1]之前的丑数乘以5，求出第一个积大于ugly[count-1]的值并保存在chenFive中I ) if(ugly[I]*5ugly[count-1] ) {chenFive=ugly[i]*5； 黑； }}//chenTwo，chenThree，chenFive的最小值是一个新的丑数，存储在ugly数组中的ugly[count]=compare(chentwo，chenThree，chenFive )； 出局； if(count==n ) /第n个丑数return ugly[count-1]； }}void main () {int N=0； scanf('%d '，n )； clock_t start=clock (； printf('%dn '，findUgly(N ) )； clock_t stop=clock (； printf(':%lf(n )，) stop - start )/CLOCKS_PER_SEC )； }
如果输入N=1400，则所需时间不到0.1秒。 可见算法2的速度无法与算法1相比。 这是用空间换取效率的结果。
转载于：https://www.cn blogs.com/Xiao gu a918/p/4181577.html