素数筛选方法-Eratosthenes法

一般步骤为：

1. 找到 p<=sqrt(n)的所有素数，
2. 删除每个素数的倍数

import java.util.*;
public class Eratosthenes {
    
    public boolean isPrime(int num) {
        // p <= sqrt(num)
        int endBounds = (int) Math.sqrt(num);
        for (int i = 2; i <= endBounds; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    
    public List eratosthenes(int num) {
        //1.获得小于 sqrt（num）的值，初始化了一些变量
        int bounds = (int) Math.sqrt(num);
        Set primeSet = new HashSet<>(); //用来存小于 bounds 范围内的素数
        Set resultSet = new HashSet<>();// 用来存素数集的倍数的编号，之所以用集合是因为各个素数的倍数可能有重复的，集合可去重
        List resultList = new linkedList<>();//结果集
        //2.获取在 bounds 范围内的所有素数
        for (int i = 2; i <= bounds; i++)
            if (isPrime(i)) primeSet.add(i);
        //3. 找到 每个素数的 小于 num的倍数的下标（值）
        for (Integer primeTemp : primeSet)
            for (int i = 2; primeTemp * i <= num; i++)
                resultSet.add(i * primeTemp);
        //4. 遍历从2-num，将不在resultset中的元素放到结果list里，就是去除素数的倍数的元素。
        for (int i = 2; i <= num; i++) {
            if (resultSet.contains(i)) continue;
            resultList.add(i);
        }
        return resultList;
    }

    public static void main(String[] args) {
        Eratosthenes eratosthenes = new Eratosthenes();
        List res = eratosthenes.eratosthenes(10000);
        System.out.println(res);
        System.out.println(res.size());
    }
}