1. 



/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #136 (Ugly Numbers)
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72
*
* @author Fabian Seidl
* @author Marcel Sachse
* @version 1.0, 03/25/2009
*
* Status : Accepted
* Runtime: 0.090
*/


public class Main
{
public static void main(String[] args)
{
int[] ugly = new int[1500];

ugly[0]=1;

// n¦chste zahl suchen
int index=0;
int searchstart = 0;

while(index<1499)
{
// n¦chste zahl suchen

int last = ugly[index];
int next = Integer.MAX_VALUE;

for(int i=searchstart;i<=index;i++)
{
int n;

// suche kleinstm¨gliche komb. aus bish. zahlen * 2,3,5

n = ugly[i]*2;
if(n<next && n>last) next = n;

n = ugly[i]*3;
if(n<next && n>last) next = n;

n = ugly[i]*5;
if(n<next && n>last)
{
next = n;

// nachdem ugly[i] * 5 verwendet wurde m¾ssen
// alle davor nicht weiter beachtet werden
searchstart = i;
}
}

// gefundene Zahl speichern
index++;
ugly[index] = next;
}

System.out.println("The 1500'th ugly number is "+ugly[1499]+".");

}

}