素数相关

1. 判断素数

利用素数集中在 6 附近的特点，进行快速判断。

 1 /*
 2  * 判断素数
 3  * 除了 2 和 3，其他的素数都在 6 附近，可以据此加快判断的速度
 4  * */
 5 private boolean isPrime(int n) {
 6     if (n == 1) {
 7         return false;
 8     }
 9     if (n == 2 || n == 3) {
10         return true;
11     }
12     if (n % 6 != 1 && n % 6 != 5) {
13         return false;
14     }
15     int n_sqrt = (int) Math.sqrt(n);
16     for (int i = 5; i <= n_sqrt; i += 6) {
17         if (n % (i) == 0 || n % (i + 2) == 0) {
18             return false;
19         }
20     }
21     return true;
22 }

2. 埃氏筛

使用 Bitmap 实现，节省空间

缺点：一个数会被筛多次

复杂度：$O(nloglogn)$

 1 /*
 2  * 用 Bitmap 实现埃氏筛。
 3  * */
 4 BitSet eratosthenes_bitmap(int n) {
 5     BitSet bs = new BitSet(n + 1);
 6     bs.set(0,n + 1,true);
 7     bs.set(0,false);
 8     bs.set(1,false);
 9 
10     int n_sqrt = (int) Math.sqrt(n);
11     for (int i = 2; i <= n_sqrt; i++) {
12         if (bs.get(i)) {
13             for (int j = i * i; j <= n; j += i) {
14                 bs.set(j,false);
15             }
16         }
17     }
18 
19     return bs;
20 }

3. 线性筛

特点：一个合数只被它的最小质因子筛一次，速度更快

如何实现：

保存过程中得到的所有素数以及素数的个数

这些保存的素数用于筛掉那些合数，在下面的代码中，每个合数不是被 $i$ 筛掉的，而是被位于 $primes$ 数组中的、合数对应的最小质因子筛掉的，$i$ 只是起到一个倍数的作用

$bs.set(i * primes.get(j), false);$

而为了保证合数可以被最小质因子筛掉，$i%p$ 的判断是必要的

复杂度：$O(n)$

 1 /*
 2  * 用 Bitmap 实现线性筛
 3  * */
 4 BitSet linear_bitmap(int n) {
 5     BitSet bs = new BitSet(n + 1);
 6     bs.set(0, n + 1, true);
 7     bs.set(0, false);
 8     bs.set(1, false);
 9 
10     int numOfPrimes = 0;
11     List<Integer> primes = new ArrayList<>();
12     for (int i = 2; i <= n; i++) {
13         if (bs.get(i)) {
14             primes.add(i);
15             numOfPrimes++;
16         }
17         for (int j = 0; j < numOfPrimes && i * primes.get(j) <= n; j++) {
18             bs.set(i * primes.get(j), false);
19             if (i % primes.get(j) == 0) {
20                 break;
21             }
22         }
23     }
24 
25     return bs;
26 }

参考：https://blog.csdn.net/qq_39763472/article/details/82428602