LeetCode Notes_#204_计数质数
Contents
题目
解答
方法1:暴力（超时）
最容易想到的方法，当然就是暴力遍历[2,n - 1]范围内所有数字。
对于每一个数字i，又将其传入辅助函数isPrime(),对[2,i - 1]的每个数字求余，如果遇到余数为0的情况，返回false。否则返回true。
class Solution {
public int countPrimes(int n) {
int count = 0;
for(int i = 2;i < n;i++){
if(isPrime(i)) count++;
}
return count;
}
boolean isPrime(int n){
for(int i = 2;i < n;i++){
if(n % i == 0) return false;
}
return true;
}
}复杂度分析
时间复杂度：O(n2)
空间复杂度：O(1)
方法2:暴力法优化1
其实上边的暴力解法稍加优化就可以ac（虽然速度依然慢）。
这个优化的思路就是，在isPrime()辅助方法当中，不需要遍历到n - 1,只需要遍历到sqrt(n)就可以了。
原因如下，以n=12为例，其实以sqrt(12)作为分界点，后边的乘积的数字组合和前边的乘积的数字组合刚好是颠倒的。
对于isPrime(int n)当中的n,如果在[2,sqrt(n)]范围内没有发现可以整除n的数字，就说明n一定是质数。
12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2class Solution {
public int countPrimes(int n) {
int count = 0;
for(int i = 2;i < n;i++){
if(isPrime(i)) count++;
}
return count;
}
boolean isPrime(int n){
//只需要遍历到sqrt(n)即可
for(int i = 2;i * i <= n;i++){
if(n % i == 0) return false;
}
return true;
}
}复杂度分析
时间复杂度：O(n* sqrt(n))
空间复杂度：O(1)
方法3:暴力法优化2
还有一种优化的方法，是排除法，具体来说就是：
质数的倍数肯定不是质数，这样就可以把所有的非质数排除，剩下的数字就是质数。
class Solution {
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
//将整个数组都初始化为true,之后开始“排除法”，即将非质数位置置为false
Arrays.fill(isPrime, true);
for(int i = 2;i < n;i++){
if(isPrime[i]){
//将i的所有倍数的索引位置设置为false
for(int j = 2*i;j < n;j += i){
isPrime[j] = false;
}
}
}
//最后再进行一次计数即可
int count = 0;
for(int i = 2;i < n;i++){
if(isPrime[i]) count++;
}
return count;
}
}复杂度分析
时间复杂度：外层循环是O(n),内层循环不太好分析...
空间复杂度：O(1)
方法4:进一步优化：Sieve of Eratosthenes(厄拉多塞筛法)
在方法3的基础上，进一步优化的方法是，将外层循环的遍历范围修改为[2, sqrt(n)]。
见如下图解。
对于n=100的情况，外层循环只需要遍历[2,sqrt(n)]即可，原因是，对于所有10以后的数字，要乘以一个数，乘积小于100，那么必然是小于10的数。所以就是类似方法2当中，出现了乘积组合的重复。
其实只需要计算[2,sqrt(n)]范围内数字的倍数就行了，之后的其他数字的倍数，都是[2,sqrt(n)]范围内数字倍数的重复。
class Solution {
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
//将整个数组都初始化为true,之后开始“排除法”，即将非质数位置置为false
Arrays.fill(isPrime, true);
//将这里的范围修改为[2, sqrt(n)]
for(int i = 2;i * i <= n;i++){
if(isPrime[i]){
//将i的所有倍数的索引位置设置为false
for(int j = 2*i;j < n;j += i){
isPrime[j] = false;
}
}
}
//最后再进行一次计数即可
int count = 0;
for(int i = 2;i < n;i++){
if(isPrime[i]) count++;
}
return count;
}
}复杂度分析
时间复杂度：O(N * loglogN)
空间复杂度：O(1)
总结
这道题其实方法2是最容易想到的，但是其实还可以逐步优化，其实方法4也并不是最优的，看评论区当中还有一些其他的“筛”法，效果更优。