蓝桥杯 幸运数

题目

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

首先从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

输入样例2

30 69

输出样例2

8

思路

观察规律题，按照题目的规律来：一步一步删掉筛选的数据，最后统计筛选出来的list剩下多少个。

代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList();
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int j = 2;
        Main.a(list, list.get(2), 2);
        Main.b(list);
        while (Main.a(list, list.get(j), j)) {
            Main.b(list);
            j++;
        }
        int item = 0;
        for (Integer integer : list) {
            if (integer.compareTo(m) > 0 && integer.compareTo(n) < 0) {
                item++;
            }
        }
        System.out.println(item);
    }
    
    public static boolean a(List<Integer> list, int k, int j) {
        boolean item = false;
        for (int i = j; i < list.size(); i++) {
            if (i % k == 0) {
                list.set(i, 0);
                item = true;
            }
        }
        return item;
    }
    
    public static void b(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            if (i != 0 && list.get(i) == 0) {
                list.remove(i);
            }
        }
    }
}