Ugly Numbers
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 21918 Accepted: 9788
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
打表记录即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
const LL MAX = 1e15;
LL a[15500];
int main()
{
LL b,c,d;
int top=0;
//freopen("output.txt","w",stdout);
for(int i=0;i<=30;i++)
{
if(i==0)
{
b=1;
}
else
{
b*=2;
}
if(b>MAX)
{
break;
}
for(int j=0;j<=30;j++)
{
if(j==0)
{
c=1;
}
else
{
c*=3;
}
if(b*c>MAX)
{
break;
}
for(int k=0;k<=30;k++)
{
if(k==0)
{
d=1;
}
else
{
d*=5;
}
if(b*c*d>MAX)
{
break;
}
a[top++]=b*c*d;
//printf("%lld\n",b*c*d);
}
}
}
sort(a,a+top);
int n;
while(scanf("%d",&n)&&n)
{
printf("%lld\n",a[n-1]);
}
return 0;
}