质数筛法
引入
原题链接：P3912 素数个数 - 洛谷
求 \(1\sim n\) 有多少个质数
朴素求法，时间复杂度 \(O(n\sqrt{n})\)
import java.util.Scanner;
public class Main {
static boolean isPrime(int x) {
if (x < 2) return false;
for (int i = 2, sqrt = (int) Math.sqrt(x); i <= sqrt; ++i)
if (x % i == 0) return false;
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (isPrime(i)) ++cnt;
}
System.out.println(cnt);
}
}
时间复杂度太高，考虑其他解法
埃氏筛
对于任意一个大于 \(1\) 的正整数 \(x\)，那么他的 \(k\) 倍一定是合数（\(k>1\)），因为该数可以表示成 \(k\times x\)。
利用这个结论，如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
时间复杂度 \(O(n\log\log n)\)
实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
boolean[] isPrime = new boolean[n + 1];
// 初始化2~n均为素数，逐个筛去
for (int i = 2; i <= n; ++i) isPrime[i] = true;
for (int i = 2; i <= n; ++i) {
for (int j = 2 * i; j <= n; j += i) {
isPrime[j] = false;
}
}
int cnt = 0;
for (boolean is : isPrime)
if (is) ++cnt;
System.out.println(cnt);
}
}
优化
一、只筛质数的倍数
对于一个合数 \(a\times b\)
如果 \(a\) 是合数，且 \(a\) 是被 \(x\) 筛去的
那么合数 \(a\times b\) 会在筛 \(x\) 的倍数时被筛去
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; ++i) isPrime[i] = true;
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) {
for (int j = 2 * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
int cnt = 0;
for (boolean is : isPrime)
if (is) ++cnt;
System.out.println(cnt);
}
}
二、内循环从 \(i^2\) 筛其倍数
对于一个合数 \(a\times b\)，其中 \(a>b>1\)
在用 \(b\) 筛掉这个合数之前，一定会被 \(a\) 先筛去，即一个合数会先被其较小的因子筛去
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; ++i) isPrime[i] = true;
for (int i = 2; i <= n; ++i) {
// 要注意乘法是否会超出int范围
if (isPrime[i] && (long) i * i <= n) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
int cnt = 0;
for (boolean is : isPrime)
if (is) ++cnt;
System.out.println(cnt);
}
}
三、外循环只筛至 \(\sqrt n\)
上一个优化中提到，一个合数会先被其较小的因子筛去。
而对于 \([\sqrt n,n]\) 内的数均会被小于 \(\sqrt n\) 的因子筛去
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; ++i) isPrime[i] = true;
for (int i = 2, sqrt = (int) Math.sqrt(n); i <= sqrt; ++i) {
if (isPrime[i] && (long) i * i <= n) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
int cnt = 0;
for (boolean is : isPrime)
if (is) ++cnt;
System.out.println(cnt);
}
}
四、只筛奇数
我们知道除 \(2\) 以外的偶数均不是合数，因为所有偶数都可以写成 \(2\times x\) 的形式
对此，可以选择只筛奇数
奇数可以表示为 \(2\times x+1\)，其中 \(x\in N\) ，\(x\) 对应质数表的下标
因此，一个数 \(n\) ，判断其是否为质数时，寻找下标为 \(\lfloor\dfrac{n}{2}\rfloor\) 的质数表所对应的值即可。
对于数组长度：
-
当 \(n\) 为偶数时，\(1\sim n\) 中最大的奇数为 \(n-1\)
要用 \(2\times idx+1\) 表示 \(n-1\)，即 \(idx_{max}=\dfrac{n-2}{2}\)
因此需要空间个数为 \(\dfrac{n-2}{2}+1=\dfrac{n}{2}\) -
当 \(n\) 为奇数时，\(1\sim n\) 中最大的奇数为 \(n\)
要用 \(2\times idx+1\) 表示 \(n\)，即 \(idx_{max}=\dfrac{n-1}{2}\)
因此需要空间个数为 \(\dfrac{n-1}{2}+1=\dfrac{n+1}{2}\)
综上，需要数组空间为 \(\lceil\dfrac{n}{2}\rceil=\lfloor\dfrac{n+1}{2}\rfloor\)
注意此时每次增量应为原来的两倍
import java.util.Scanner;
public class Main {
static boolean[] primeTable;
static void initialize(final int n) {
primeTable = new boolean[(n + 1) / 2];
for (int i = 1; i < primeTable.length; ++i) primeTable[i] = true;
for (int i = 3, sqrt = (int) Math.sqrt(n); i <= sqrt; i += 2) {
if (primeTable[i / 2] && (long) i * i <= n) {
for (int j = i * i; j <= n; j += 2 * i) {
primeTable[j / 2] = false;
}
}
}
}
static boolean isPrime(int x) {
if (x % 2 == 0) return x == 2;
return primeTable[x / 2];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
initialize(n);
int cnt = n < 2 ? 0 : 1;
for (boolean is : primeTable)
if (is) ++cnt;
System.out.println(cnt);
}
}
五、将数组意义改为不是素数
数组定义为如果为 \(true\) ，则它不是素数，这样可以不用自己初始化，编译器默认初始化为 \(false\)。
import java.util.Scanner;
public class Main {
static boolean[] notPrime;
static void initialize(final int n) {
notPrime = new boolean[(n + 1) / 2];
if (n > 0) notPrime[0] = true;
for (int i = 3, sqrt = (int) Math.sqrt(n); i <= sqrt; i += 2) {
if (!notPrime[i / 2] && (long) i * i <= n) {
for (int j = i * i; j <= n; j += 2 * i) {
notPrime[j / 2] = true;
}
}
}
}
static boolean isPrime(int x) {
if (x % 2 == 0) return x == 2;
return !notPrime[x / 2];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
initialize(n);
int cnt = n < 2 ? 0 : 1;
for (boolean is : notPrime)
if (!is) ++cnt;
System.out.println(cnt);
}
}
线性筛
埃氏筛仍有优化思路，因为一些合数可能会被多个因子筛去
算术基本定理
任何一个大于 \(1\) 的自然数 \(N\)，如果 \(N\) 不为质数，那么 \(N\) 可以唯一分解成有限个质数的乘积 \(N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\cdots P_n^{an}\)，这里 \(P_1<P_2<P_3\cdots<P_n\) 均为质数，其中指数 \(a_i\) 是正整数。这样的分解称为 \(N\) 的标准分解式。
我们选择用每个合数的最小质因子（或者说用这个合数的最大的因子）来筛去这个合数
这样就保证了每个合数只被筛去一次，那么时间复杂度就降低至 \(O(n)\) 了
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
int[] primes = new int[(n + 1) / 2];
boolean[] isPrime = new boolean[n + 1];
int tot = 0;
for (int i = 2; i <= n; ++i) isPrime[i] = true;
for (int i = 2; i <= n; ++i) {
if (isPrime[i]) primes[tot++] = i;
for (int prime : primes) {
if (prime * i > n) break;
isPrime[prime * i] = false;
if (i % prime == 0) break;
}
}
System.out.println(tot);
}
}
PS：注意到筛法求素数的同时也得到了每个数的最小质因子，这是筛法求积性函数的铺垫