Ugly Numbers, UVa 136

---

题目

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 1500th ugly number.

Input

There is no input to this program.

Output

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

---

题意

丑数是指不能被2,3,5以外的其他素数整除的数，本题要求从小到排列的丑数中第1500个。

分析

书中方法定义了一个“越小的整数优先级越大的优先队列”，定义方法为：

priority_queue<int,vector<int>,greater<int> > pq;

最后两个“>”不要写在一起，以防编译器认作“>>”。 因为2x,3x,5x仍为丑数，每次将pq中最小丑数出队并乘2,3,5形成新的丑数加入队列，以求出第1500个丑数。

---

代码实现

#include<cstdio> #include<iostream> #include<sstream> #include<algorithm> //STL #include<string> #include<map> #include<set> #include<vector> #include<iterator> #include<stack> #include<queue> #include <functional> using namespace std; typedef long long LL; const int coeff[3] = { 2,3,5 }; int main() { priority_queue<LL, vector<LL>, greater<LL> > pq; set<LL> s; pq.push(1); s.insert(1); for (int i = 1;; i++) { LL x = pq.top(); pq.pop(); if (i == 1500) { cout << "The 1500'th ugly number is " << x <<".\n"; break; } for (int j = 0; j < 3; j++) { LL x2 = x*coeff[j]; if (!s.count(x2)) { s.insert(x2); pq.push(x2); } } } return 0; }

---

遇到的问题

使用priority_queue<LL, vector<LL>, greater<LL> > pq;时报错“greater”不是模板，加入#include <functional>后解决。