例题5-7 丑数

最新推荐文章于 2021-08-16 02:24:50 发布

摩霄志在潜修羽

最新推荐文章于 2021-08-16 02:24:50 发布

阅读量819

点赞数

本文链接：https://blog.csdn.net/cprimesplus/article/details/86759598

版权

暴力求解法专栏收录该内容

13 篇文章

订阅专栏

【描述】
丑数是指不能被2，3，5以外的其他素数整除的数。把丑数从小到大排列起来，结果如
下：
1,2,3,4,5,6,8,9,10,12,15,…
求第1500个丑数。

【思路】
从小到大依次生成。
最基础的丑数是1，而后的所有丑数都是在这个基础上生成的。
如果按照正向思维分析，需要考虑除2，3，5以外的所有素数–这显然不切实际。

因此考虑派生的性质：假设一个丑数为x，那么2x，3x，5x也都是丑数。

这样，就可以使用一个优先队列保存所有已经生成的丑数，每次取出最小的丑数，以使密集生成三个新的丑数。

【代码】

//丑数，2x,3x,5x
#include<iostream>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<cstring>
using namespace std;
typedef long long LL;
const int coeff[3] = { 2,3,5 };
int main()
{	
	
	set<int>ss;
	priority_queue<LL, vector<LL>, greater<LL> >pq;
	pq.push(1);
	ss.insert(1);
	for (int i = 1;;i++)
	{
		LL x = pq.top();pq.pop();
		if (1500 == i) {
			cout << x << endl;
			break;
		}
		for (int j = 0;j < 3;j++)
		{
			LL t = x * coeff[j];
			if (!ss.count(t)) {
				pq.push(t);
				ss.insert(t);
			}
		}
	}
	return 0;
}