线性筛选法求素数——模板

 1 package com.lzp.util.algorithm.template;
 2 
 3 import java.util.Arrays;
 4 
 5 /**
 6  * @Author LZP
 7  * @Date 2021/5/29 16:12
 8  * @Version 1.0
 9  */
10 public class Prime {
11 
12     private static int[] primes;
13     private static boolean[] flag;
14 
15     public static void main(String[] args) {
16         prime(90);
17         System.out.println(Arrays.toString(primes));
18     }
19 
20     public static void prime(int n) {
21         primes = new int[n + 10];
22         flag = new boolean[n + 10];
23         // 线性筛选法求素数
24         int cnt = 0;
25         for (int i = 2; i <= n; i++) {
26             if (!flag[i]) {
27                 // 表示没有被筛选掉，就添加到素数数组中
28                 primes[cnt++] = i;
29             }
30             // 开始线性筛选该数的倍数
31             for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
32                 // 筛选
33                 flag[primes[j] * i] = true;
34             }
35         }
36     }
37 }