&蓝桥杯-幸运数_蓝桥 幸运数

题目描述:

　幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。

　　首先从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
　　程序输出：
　　8

题解:        在n范围内对数据进行删除(利用vector数组删除功能),然后通过二分查找确定(M,N)区间

#include<bits/stdc++.h>
using namespace std;
int m,n;
int len1=1;          //len1为>n范围内的数组长度
vector<int>a;        //vector数组方便删除元素
 
 
//二分查找
int bin_find(int m){    
	int l=1;int r=len1;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]<m)l=mid+1;
		else r=mid-1;
	}
	return l;
}
int main(){
	cin>>m>>n;
	a.resize(16700);
	a[0]=0;
	for(int j=1;a[len1-1]<=n;j++,len1++){    //利用通过幸运数2,3事先缩减数组的长度
		if(j%3==0)j++;	                 
		a[len1]=2*j-1;
	}
	len1--;
	for(int h=3;len1>a[h];h++){            //h为幸运数的位置 
		for(int i=a[h];i<len1;i+=a[h]){
			a.erase(a.begin()+i);           //利用vector来删除数组中特定序号的元素
			len1--;
			i--;
		}
	}
	int i1=bin_find(n),i2=bin_find(m);    //通过二分查找确定区间
	if(a[i2]>m)i2--;
	cout<<i1-i2-1;
}