## 2008年9月26日

### 136 - Ugly Numbers

UVa網站題目連結
My Solved Problems Performance

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, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

## Input and Output

There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.

## Sample output

The 1500'th ugly number is <number>.

## Solution

`public class Main {    public static void main (String[] args) {        int size = 1500;        int counter = 1;        int result = 0;        for (int i=2; counter<size; i++) {            int x = i;            while ((x%5==0)) {                x/=5;            };            while ((x%3==0)) {                x/=3;            };            while ((x%2==0)) {                x/=2;            };            if (x==1) {                counter++;            }            if (counter == size) result = i;        }        System.out.println("The 1500'th ugly number is " + result + ".");        // The 1500'th ugly number is 859963392.    }}`