import java.util.ArrayList;
import java.util.List;
//算法原理：从2开始，将[2, 根号n]中每个素数当作最小质因数去标记合数，剩下的就都是素数。（对比埃氏筛法理解）
//时间复杂度：O(n)
/*
  算法中break那行代码的原理最难理解，作用就是弥补埃氏筛法的不足，防止重复筛除合数。

  代码含义：如果当前素数primes.get(j)是数字i的最小质因数，那么后面的素数就不可能是数字i及其倍数的最小质因数。

  举个例子：假如当前数字是8，当前素数是2，理应跳出循环。如果继续，那么下一个素数是3，所以8*3=24 ，但是24的最小质因数是2不是3，再继续8*4=32 ，32的最小质因数是2不是5，以此类推，可以发现8及其倍数的最小质因数都应该是2，所以到2这里就应该跳出循环了。
*/
public class Primes {
    public static List<Integer> getPrimes(int num){
        List<Integer> list = new ArrayList<>();
        if(num == 0 || num == 1){
            return list;
        }
        boolean[] tags = new boolean[num+1];
        //true代表不是素数
        tags[0] = true;
        tags[1] = true;
        for(int i = 2; i <= num;i++){
            if(!tags[i]){
                list.add(i);
            }
            for(int j = 0; j < list.size() && i * list.get(j) <= num; j++){
                tags[i * list.get(j)] = true;
                if(i % list.get(j) == 0){
                    break;
                }
            }
        }
        System.out.println(list.size());
        return list;
    }

    public static void main(String[] args) {
        List<Integer> primes = getPrimes(1000000000);
        System.out.println(primes);
    }
}