在刷题过程中，遇到了寻找小于等于k的所有质数，来记录下通用的两个常见解法：
1. 开方降低时间复杂度
class Solution { public int countPrimes(int n) { int ans = 0; for (int i = 2; i < n; ++i) { ans += isPrime(i) ? 1 : 0; } return ans; } public boolean isPrime(int x) { for (int i = 2; i * i <= x; ++i) { if (x % i == 0) { return false; } } return true; } }
2. 埃氏筛法
// 如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，因此我们可以从这里入手。 // 从最小的质数开始，从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身）， class Solution { public int countPrimes(int n) { int[] isPrime = new int[n]; Arrays.fill(isPrime, 1); int ans = 0; for (int i = 2; i < n; ++i) { if (isPrime[i] == 1) { ans += 1; if ((long) i * i < n) { for (int j = i * i; j < n; j += i) { isPrime[j] = 0; } } } } return ans; } }
3. 线性筛
// 优化的目标是让每个合数只被标记一次 class Solution { public int countPrimes(int n) { List<Integer> primes = new ArrayList<Integer>(); int[] isPrime = new int[n]; Arrays.fill(isPrime, 1); for (int i = 2; i < n; ++i) { if (isPrime[i] == 1) { primes.add(i); } for (int j = 0; j < primes.size() && i * primes.get(j) < n; ++j) { isPrime[i * primes.get(j)] = 0; if (i % primes.get(j) == 0) { break; } } } return primes.size(); } }
