## Saturday, August 28, 2010

### poj_1338_UglyNumbers.cpp

poj1338, UVa00136,

## Problem:

Ugly Numbers
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 13375 Accepted: 5897
Description
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n'th ugly number.
Input
Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.
Output
For each line, output the n’th ugly number .:Don’t deal with the line with n=0.
Sample Input
```1
2
9
0```
Sample Output
```1
2
10```
Source
New Zealand 1990 Division I,UVA 136

## Solution:

The alternative way is just print out the answer: 859963392.

## Source Code:

#include<stdio.h>
int r;
int Min(int a,int b,int c){
if(a<b)b=a;
if(b<c)c=b;
return c;
}
int main(){
int a;
int b;
int c;
int i;
r=1;r=2;r=3;r=4;r=5;
a=3; b=2;  c=2
for(i=6;i<=1500;i++){
r[i]=Min(r[a]*2,r[b]*3,r[c]*5);
for(;r[a]*2<=r[i];a++);
for(;r[b]*3<=r[i];b++);
for(;r[c]*5<=r[i];c++);
}
scanf("%d",&i);
while(i){
printf("%d\n",r[i]);
scanf("%d",&i);
}
return 0;
}