因子问题 I

题目：

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

There is no input to this program.

Output

Output should consist of a single line as shown below, with ‘’ replaced by the number computed. Sample Output The 1500'th ugly number is .

AC代码：

#include <iostream>
using namespace std;
int min1 (int a,int b)
{return a<b?a:b;}//自定义函数
int main()
{
long long a[1500];
a[0] = 1;
long long a2=0,a3=0,a5=0;
for(int i=1;i<1500;i++)
{
while(a[a2]*2<=a[i-1]) a2++;
while(a[a3]*3<=a[i-1]) a3++;
while(a[a5]*5<=a[i-1]) a5++;
a[i]= min1(min1(a[a2]*2,a[a3]*3),a[a5]*5);
}
cout<<"The 1500'th ugly number is "<<a[1499]<<'.'<<endl;
}

做此类数学题一定要冷静啊！

不要首先想着捷径，一定要先想正轨，更容易解出来