埃氏筛法求解质数模板

一般求解1~n范围内（不包括n）的质数常见的有两种方法：线性筛和埃氏筛法，求解出所有的质数之后需要将其存储到某个数据结构中，对于n不是特别大的时候线性筛还是有效的，但是一旦当n超过某个规模的时候线性筛就会变得很慢，有可能计算不出来，这个时候就需要使用到埃氏筛法，埃氏筛法的一个核心是将声明一个长度为n的标记数组，将质数对应的倍数全部标记为1，质数的倍数肯定是合数，所以只有当前位置对应的值为0的时候说明当前位置i是一个素数，将其加入到结果集中即可，在java语言中埃氏筛法对于n = 10 ^ 8内的质数还是可以计算出来的（如果python语言的话则需要计算很久），比10 ^ 8大一点的数字需要几秒就可以计算出来，所以当n在10 ^ 8之内的数字埃氏筛法还是非常有效的，我们可以记住代码的模板在用的时候可以直接写出来：

import java.util.ArrayList;
import java.util.List;
public class Main {
    // 求解1 ~ n范围的质数并且返回求解的质数列表
    public static List<Integer> getPrimes(int n){
        int vis[] = new int[n];
        List<Integer> primes = new ArrayList<Integer>();
        for (int i = 2; i < n; ++i){
            if (vis[i] == 0){
                primes.add(i);
                for (int j = i + i; j < n; j += i){
                    vis[j] = 1;
                }
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int n = 1000;
        // int n = 100000000;
        List<Integer> res = getPrimes(n);
        for (int i = 0; i < res.size(); ++i){
            int t = res.get(i);
            if (i > 0 && i % 10 == 0) System.out.println();
            System.out.print(t + " ");
        }
    }
}