?该题意上需要注意的是 我们是先找到所有的将被删除的数字再全部一起删除，而不是一边找一边删，这样会导致下标错位
我的第一思路也比较简单，按照题目意思来，先找到幸运数，再标记需要删除的数字，再将它们全部删除即可
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <iomanip>
#include<cmath>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
using namespace std;
int main()
{
int n, m, lucky = 1, j = 1,ans=0;
cin >> n >> m;
vector<int>nums(m+5);//需要多少开多少
for (int i = 1; i <= m; i++)
{
nums[i] = i;//初始化
if (i % 2 == 0)
{
nums[i] = -1;标记
}
}
for (vector<int>::iterator it=nums.begin();it!=nums.end();it++)//缩紧
{
if (*(it) == -1)//删除标记的元素
{
it=nums.erase(it);
}
}
上面这里是先进行需要删除序号是2的数字
while (nums[lucky]!=0)//如果以幸运数为下标的数字为0，则后面没有数字了
{
lucky = nums[++j]; //找到幸运数
for (int i = j; i <= m; i++)//标记要删除的
{
if (nums[i] == 0)//已经没有数字了
{
break;
}
if (i % lucky == 0)
{
nums[i] = -1;//标记数字
}
}
//缩紧
for (vector<int>::iterator it = nums.begin()+1; it != nums.end(); it++)
{
if (*(it) == -1)
{
it = nums.erase(it);//注意这里erase的使用
}
}
}
for (int i = 1; i < nums.size(); i++)
{
if (nums[i] == 0)//已经遍历完所有所剩数字
{
break;
}
if (nums[i] > n && nums[i] < m)//在范围内（开区间）
{
ans++;
}
}
cout << ans << endl;
return 0;
}实际上该题也可用DFS解决
这里我们每次以幸运数开始往后面剩余的数字搜索，每次都采用间接删除序号能被幸运数整除的数字（这里的间接删除指的是我们只有在序号不被整除的时候才访问数组），直至到达dfs出口，这里我们数组元素全部初始化为0，所以出口便是幸运数为0的时候
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int a[N];
int m,n;
void dfs(int v){
if(a[v]==0){
return;
}
else{
int j=1;
for(int i=1;i<n;i++){
if(i%a[v]){//只有不被幸运数整除的数才进数组（间接删除）
a[j++]=a[i];
}
}
dfs(++v);//更新幸运数
}
}
int main(){
int j=1;
scanf("%d%d",&m,&n);
for(int i=1;i<n;i++){//先将序号可以被2整除的元素删去
if(i%2){//只有不被2整除的数才进数组（间接删除）
a[j++]=i;
}
}
dfs(2);//搜索
int ans=0,i=1;
while(a[i]){//遍历剩下的数字
if(a[i]>m&&a[i]<n){//在所求范围内
ans++;
}
i++;
}
cout<<ans;
return 0;
}
