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>.
题目类型：数学题
算法分析：本题使用了优先队列和集合来计算。用一个优先队列来保存生成的丑数，每次取出最小的丑数来生成三个新的丑数。将新生成的不重复的丑数插入到集合中和优先队列中。由于每次取出优先队列的对头元素是最小的，则只需要取1500次对头元素即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <cstdio> #include <iostream> #include <fstream> #include <set> #include <queue> #include <vector> using namespace std; const int coeff[] = {2, 3, 5}; int main() { priority_queue <long long, vector <long long>, greater <long long> > pq; set <long long > s; s.insert (1); pq.push (1); int i; for (i = 1; ; i++) { long long val1 = pq.top (); pq.pop (); if (i == 1500) { printf ("The 1500'th ugly number is %lld.\n", val1); break; } int j; for (j = 0; j < 3; j++) { long long temp = val1 * coeff[j]; if (!s.count (temp)) { s.insert (temp); pq.push (temp); } } } return 0; } |