【蓝桥杯】历届试题幸运数（向量筛）

本文主要是介绍【蓝桥杯】历届试题幸运数（向量筛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

历届试题幸运数

问题描述
幸运数是波兰数学家乌拉姆命名的，它采用与生成素数类似的“筛法”生成
首先从1开始写出自然数1,2,3,4,5,6,…
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除，变为：
1 _ 3 _ 5 _ 7 _ 9 ……
把它们缩紧，重新记序，为：
1 3 5 7 9 …… 这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, …
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,…)
最后剩下的序列类似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …

输入格式：输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
输出格式：程序输出位于m和n之间的幸运数的个数（不包含m和n）。

样例输入：1 20
样例输出：5

样例输入：30 69
样例输出：9（题目中的输出是8，但是测试证明，确实应该是9）

---分割线---

分析：
无论是题目给的提示，还是“幸运数”生成描述，都在很直接的告诉你——要用筛法
我们确实也应该从这里出发
最开始我的想法是数组，但是数组种元素的缺减会导致之后的大量元素整体后移
这极有可能超时，并且数组操作极为不便

于是想到用向量（向量中元素缺减也会导致大量元素整体后移，但是其用到了堆排序，在调整时速度远远快于数组），反正既然有现成的数据结构，为什么你还要去自己写呢？

最后说一下我的解题思路
首先，建立一个向量v，然后利用循环，将输入数据n作为向量中的上限（即1-n）将其整体纳入v中。
接着，建立一个最外层while循环（退出条件为当前取出的幸运数大于向量长度）
而在此循环中的内容则为一个永真循环（目的是将当前向量进行一个筛选，选出每一次从向量头到向量尾中，应该被舍弃掉的那些数）
注意：这个永真循环中的具体实现方式是利用一个错位的过程（错位是指将应该保留下来的数字跳过，而那些该移除的数字则被删除掉）来控制向量中数据的留与删。
在这些while循环中的最里层，我定义了一个指针来扫描向量，当这个指针越界（即p>v.size()）就会直接goto到循环外（具体见代码）。
当内部两个循环都结束之后，我们的工作有两部分：
1.更新k的值（k表示了第pos+1个幸运数）
2.更新p指针为0

这样，最后在main函数中，我就可以通过一个循环来检测出当前范围中的幸运数个数了（需要注意的是：由于在前面的筛法中我已经限制了最大值的阈值，那么在这里求幸运数个数时，我仅仅需要找到最小值的位置就行了）

废话不多说，下面直接上本题的完整代码：

---分割线---

#include<iostream>
#include<vector>
using namespace std;int pos=1,m,n;
vector<int> v;
void generate()
{for(int i=1;i<=n;i++)v.push_back(i);int k=2,p=0;			 //k表示第pos+1个幸运数（初始化为2，但不是幸运数） while(k<=v.size())		 //当k的大小已经超出了栈总长时，说明在当前范围内的幸运数已经全部找出 {while(1){int i=1;while(i<k){p++,i++;if(p<v.size()) continue;else goto lable;}v.erase(v.begin()+p);}lable: k=v[pos++];p=0;}
}int main()
{cin>>m>>n;generate();int ans=0;for(int i=0;i<v.size();i++)if(v[i]>m){ans=v.size()-i;break;}cout<<ans<<endl;return 0;
}