目录
题目描述
输入描述
输出描述
输入输出样例
题目分析:列表枚举
AC代码(Java):
题目描述
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的"筛法"生成。
首先从 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 < 10^6)。
输出描述
输出位于 m 和 n 之间的幸运数的个数(不包含 m 和 n )。
输入输出样例
输入
1 20
输出
5
题目分析:列表枚举
输入
输出
1.照例先分析题目,幸运数是从1开始的,一直往后,然后1是第一个自然数,就不管他,让第一个幸运数从2开始,就是删除所有下标能被2整除的数。
2.这里看到需要频繁删除,首先排除数组来做(用数组做也不是不行),可以用列表。
3.然后看数据范围,它给的提示是 m和n,但是幸运数是从1开始的,也就是说我们需要填充1到n的数据进列表里面。然后删除完毕之后再判断m-n范围内的数据有多少即可。
4.因为列表的特性(删除了i,那么i的位置就会被i+1补上),所以我们删除要从末尾开始,依次往前删除,也就是 从len 到 1;
5.循环读取幸运数删除即可,每次拿到幸运数,通过一个方法,逆向删除所有能被该幸运数整除的下标即可。



