xLsDg

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 unsigned long getUglyNumber( unsigned long index )
 5 {
 6     unsigned long *pMax = NULL, *pMax2 = NULL, *pMax3 = NULL, *pMax5 = NULL, *pUgly = NULL;
 7     unsigned long min = 0, max = 0, max2 = 0, max3 = 0, max5 = 0;
 8 
 9     if( 1 > index ) {
10         return ( unsigned long )0;
11     }
12 
13     pUgly = ( unsigned long* )malloc( ( size_t )index * sizeof( unsigned long ) );
14     if ( NULL == pUgly ) {
15         return ( unsigned long )0;
16     }
17 
18     pMax = pMax2 = pMax3 = pMax5 = pUgly;
19     *pUgly = 1;
20 
21     while ( pMax - pUgly < index - 1 ) {
22         max2 = *pMax2 * 2;
23         max3 = *pMax3 * 3;
24         max5 = *pMax5 * 5;
25 
26         min = ( max2 < max3 ) ? max2 : max3;
27 
28         *( ++pMax ) = ( min < max5 ) ? min : max5;
29 
30         while ( *pMax2 * 2 <= *pMax ) ++pMax2;
31         while ( *pMax3 * 3 <= *pMax ) ++pMax3;
32         while ( *pMax5 * 5 <= *pMax ) ++pMax5;
33     }
34 
35     max = *pMax;
36 
37     free( pUgly );
38 
39     return max;
40 }
41 
42 int main()
43 {
44     unsigned long index = 1500;
45     printf( "The No.%u ugly number is %u." , index, getUglyNumber( index ) );
46     return 0;
47 }
48