試題 歷屆試題 幸運數

資源限制
時間限制：1.0s 內存限制：256.0MB

---

題描述
幸運數是波蘭數學家烏拉姆命名的。它采用與生成素數類似的“篩法”生成

。
首先從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

1 20

樣例輸出1

5

樣例輸入2

30 69

樣例輸出2

8

思路：

根據題意模擬篩出需要的數據，
然后二分查找即可。
具體看代碼~

代碼：

#include <iostream> const int N = 1e6+5; using namespace std; int a[N]; bool vis[N]; //預先篩選 int solve() {int k = 0;for(int i = 1; i < 1e6; i+=2){a[++k] = i;}int id = 1;while(1){bool flag = false;int siz = k;for(int i = a[++id]; i <= siz; i+=a[id]){if(i % a[id] == 0){flag = true;vis[a[i]] = true;}}if(!flag) return k;k = 0;for(int i = 1; i <= siz; ++i){if(!vis[a[i]]) a[++k] = a[i];}} } //第一個大于v int getPos1(int k,int v) {int l = 1,r = k;int res = 0;while(l <= r){int mid = (l + r) >> 1;if(a[mid] > v){res = mid;r = mid - 1;}else l = mid + 1;}return res; }//最后一個小于v int getPos2(int k,int v) {int l = 1,r = k;int res = 0;while(l <= r){int mid = (l + r) >> 1;if(a[mid] < v){res = mid;l = mid + 1;}else r = mid - 1;}return res; }int main() {int n,m;int k = solve();cin>>m>>n;int ans = getPos2(k,n)-getPos1(k,m) + 1;cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的试题 历届试题 幸运数(二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。