企业网站建设申请域名,seo入门基础教程,如何在网站上做用工登记,免费的排版软件题目描述 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成 。 首先从1开始写出自然数1,2,3,4,5,6,… 1 就是第一个幸运数。 我们从2这个数开始。把所有序号能被2整除的项删除#xff0c;变为#xff1a; 1 _ 3 _ 5 _ 7 _ 9 … 把它们缩紧#xff0c;重…题目描述 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成 。 首先从1开始写出自然数1,2,3,4,5,6,… 1 就是第一个幸运数。 我们从2这个数开始。把所有序号能被2整除的项删除变为 1 _ 3 _ 5 _ 7 _ 9 … 把它们缩紧重新记序为 1 3 5 7 9 … 。这时3为第2个幸运数然后把所有能被3整除的序号位置的数删去。注意是序号位置不是那个数本身能否被3整除!! 删除的应该是511, 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。 样例输入
30 69
样例输出
8
解题思路 直接模拟这个过程就行了一直递归直到不能删除为止。把不能被n整除的数存放进该数组知道第n个数比他大了位置就return。
代码如下
#include iostream
using namespace std;
const int N 1e6 10;
int a[N];
int n, m;void dfs(int u) {int cnt u;if (a[u] m)return;for (int i u; i m; i)//枚举序号 {if (i % a[u])//如果序号不能被整除就是我们要的。{a[cnt] a[i];}}dfs(u 1);
}int main() {cin n m;for (int i 1; i m; i)a[i] 2 * i - 1;if (m 2)dfs(2);int ans 0;for (int i 1; a[i] m; i) {if (a[i] n)ans;}cout ans endl;return 0;
}
