想吃冰卻又敏感保護不足?來自星星的你也會打廣告?吉隆坡最便宜行程一覽表黃曉明、林志玲攜手代言...
2011-12-18 20:12:15 人氣(204) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 136 - Ugly Numbers

0
收藏
0
推薦

 Ugly Numbers 

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 <number> replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.





#include<stdio.h>
int main() {
    int DP[1500] = {1}, t2 = 0, t3 = 0, t5 = 0, tmp, i;
    for(i = 1; i < 1500; i++) {
        while(DP[t2]*2 <= DP[i-1])    t2++;
        while(DP[t3]*3 <= DP[i-1])    t3++;
        while(DP[t5]*5 <= DP[i-1])    t5++;
        tmp = DP[t2]*2;
        if(DP[t3]*3 < tmp)    tmp = DP[t3]*3;
        if(DP[t5]*5 < tmp)    tmp = DP[t5]*5;
        DP[i] = tmp;
    }
    printf("The 1500'th ugly number is %d.\n", DP[1499]);
    return 0;
}

136Ugly Numbers
台長:Morris
人氣(204) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 443 - Humble Numbers
此分類上一篇:[UVA] 10789 - Prime Frequency

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文