Ugly Numbers
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 18395 | Accepted: 8138 |
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.
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
题目大意:如果一个数的质因子只有2,3,5则该数是一个丑数,输入n求第n个丑数。
#include <stdio.h> #include <iostream> using namespace std; int main() { int result[1505] = {0, 1}; int n2 = 1, n3 = 1, n5 = 1, n; for (int i = 2; i <= 1500; i++) { result[i] = min(result[n2] * 2, min(result[n3] * 3, result[n5] * 5)); if (result[i] == result[n2] * 2) { n2++; } if (result[i] == result[n3] * 3) { n3++; } if (result[i] == result[n5] * 5) { n5++; } } while(scanf("%d", &n) != EOF && n != 0) { printf("%d ", result[n]); } return 0; }