目录
方法一：暴力法
复杂度
方法二：跨度为6的倍数的优化
复杂度
方法三：埃氏筛法
复杂度
方法四：埃氏筛法的改良
复杂度
方法五：线性筛
复杂度
性能对比测试
练习
方法一：暴力法
就是写一个函数isprime(int x)，依次判断(2,根号x)之内的数能否被x整除。然后依次调用isprime(2,n-1)。
class Solution_1 {//暴力法
public:
bool isprime_(int x) {
for (int i = 2; i * i <= x; i++)
if (x % i == 0) return false;
return true;
}
int countPrimes(int n) {
int ans = 0;
for (int i = 2; i < n; i++)
if (isprime_(i)) ans++;
return ans;
}
};复杂度
时间 O( )
空间 O(1)
方法二：跨度为6的倍数的优化
除了2，3之外，其它所有的素数(假设为x)余n后，要么是5，要么是1。
为什么呢？我们假设一个数为x
x%6==0 --> x是0或6的倍数，全都不是素数
x%6==2--> x是2的倍数，其中只有2是素数
x%6==3 --> x是3的倍数，其中只有3是素数
x%6==4 --> x是2的倍数且x>=4，全都不是素数
x%6==1 或 ||x%6==5 --> x有可能是素数
所以我们在isprime(x)函数中，在判断完特例2,3之后，从5开始，每次+6，判断能否被x整除。
同时，调用isprime函数时，也可以跨六步长。
class Solution_2 {//跨度为6的倍数的优化
public:
bool isprime(int x) {
if(x<=3) return x>1;
if (x % 2 == 0 || x % 3 == 0) return false;
for (int i = 5; i * i <= x; i += 6)
if (x % i == 0 || x % (i + 2) == 0)
return false;
return true;
}
int countPrimes(int n) {
if (n <= 2) return 0;
if (n == 3) return 1;
if (n == 4) return 2;
int ans = 2;
for (int i = 5; i < n; i += 6) {
if (isprime(i)) ans++;
if (i + 2 < n && isprime(i + 2)) ans++;
}
return ans;
}
};复杂度
时间 O()
空间 O(1)
方法三：埃氏筛法
核心思想就是：1、如果x是质数，那么x的倍数肯定不是质数。
2、如果x是合数，那么x一定是某个小于x的质数y的倍数。（这就当个结论吧）
class Solution_3 {//埃氏筛法
public:
int countPrimes(int n) {
vector<bool> isprime(n, true);
int ans = 0;
for (int i = 2; i < n; i++) {
if (isprime[i] == true) {
ans++;
for (int j = 2*i; j < n; j += i)
isprime[j] = false;
}
}
return ans;
}
};复杂度
时间：O（）
空间：O(n)
方法四：埃氏筛法的改良
观察上面的式子会发现，有些数会重复被标记。
比如说代码中的i==11时，我们从isprime[11]开始标记，isprime[11],isprime[22],……,isprime[121],……都被标记为false。
但是对于isprime[11*2],……,isprime[11*10]这9个位置来说，分别在i==2,3,4,5,6,7,8,9,10的时候就已经被标记了。有的位置甚至被重复标记不止一次，比如说isprime[11*6]，在i==2,i==3的时候都被标记了一遍，现在i==11还要被标记一遍。
为了防止以上i*i之前被重复标记的情况，在判断一个数是素数后。我们从i*i开始标记，而不是从2*i开始标记。
注意：i*i可能会造成isprime的数组越界，所以要转换成long long。
class Solution_4 {//埃氏筛法的优化
public:
int countPrimes(int n) {
int ans = 0;
vector<bool> isprime(n, true);
for (int i = 2; i < n; i++) {
if (isprime[i]) {
ans++;
long long square = (long long)i * i;
if (square < n) {
for (long long j = square; j < n; j += i)
isprime[j] = false;
}
}
}
return ans;
}
};复杂度
时间：O（）
空间：O(n)
方法五：线性筛
尽管埃氏筛的改良减少了一些重复标记的情况，但是还会有重复标记的情况。
埃氏筛的改良只能减少i*i前面的数的重复标记的情况，却不能减少i*i后面的数的重复标记的情况。
比如说isprime[45]这个位置，即使用埃氏筛的改良，还是会在i==3和i==5的时候都被标记。
因此我们要想一种方法让每一个数都只被标记一次。
算法的原理可以看力扣上第204题的题解
class Solution_5 {//线性筛法
public:
int countPrimes(int n) {
vector<int> primes;
vector<int> isPrime(n, 1);
for (int i = 2; i < n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
isPrime[i * primes[j]] = 0;
if (i % primes[j] == 0) {
break;
}
}
}
return primes.size();
}
};复杂度
时间：O(n)
空间：O(n)
性能对比测试
#include <iostream>
#include<vector>
#include<chrono>
using namespace std;
class Solution_1 {//暴力法
public:
bool isprime_(int x) {
for (int i = 2; i * i <= x; i++)
if (x % i == 0) return false;
return true;
}
int countPrimes(int n) {
int ans = 0;
for (int i = 2; i < n; i++)
if (isprime_(i)) ans++;
return ans;
}
};
class Solution_2 {//跨度为6的倍数的优化
public:
bool isprime(int x) {
if(x<=3) return x>1;
if (x % 2 == 0 || x % 3 == 0) return false;
for (int i = 5; i * i <= x; i += 6)
if (x % i == 0 || x % (i + 2) == 0)
return false;
return true;
}
int countPrimes(int n) {
if (n <= 2) return 0;
if (n == 3) return 1;
if (n == 4) return 2;
int ans = 2;
for (int i = 5; i < n; i += 6) {
if (isprime(i)) ans++;
if (i + 2 < n && isprime(i + 2)) ans++;
}
return ans;
}
};
class Solution_3 {//埃氏筛法
public:
int countPrimes(int n) {
vector<bool> isprime(n, true);
int ans = 0;
for (int i = 2; i < n; i++) {
if (isprime[i] == true) {
ans++;
for (int j = 2*i; j < n; j += i)
isprime[j] = false;
}
}
return ans;
}
};
class Solution_4 {//埃氏筛法的优化
public:
int countPrimes(int n) {
int ans = 0;
vector<bool> isprime(n, true);
for (int i = 2; i < n; i++) {
if (isprime[i]) {
ans++;
long long square = (long long)i * i;
if (square < n) {
for (long long j = square; j < n; j += i)
isprime[j] = false;
}
}
}
return ans;
}
};
class Solution_5 {//线性筛法
public:
int countPrimes(int n) {
vector<int> primes;
vector<int> isPrime(n, 1);
for (int i = 2; i < n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
isPrime[i * primes[j]] = 0;
if (i % primes[j] == 0) {
break;
}
}
}
return primes.size();
}
};
int main()
{
int n=867896;
cout<<"测试数据：n="<<n<<endl;
cout << "暴力法\t";
auto start1 = chrono::system_clock::now();
Solution_1 s1;
cout << s1.countPrimes(n) << endl;
auto end1 = chrono::system_clock::now();
auto duration1 = chrono::duration_cast<chrono::microseconds>(end1 - start1);
cout<<"暴力法耗时：\t"<<duration1.count()<<"微秒"<<endl;
cout << "跨度为6的倍数的优化\t";
auto start2 = chrono::system_clock::now();
Solution_2 s2;
cout << s2.countPrimes(n) << endl;
auto end2 = chrono::system_clock::now();
auto duration2 = chrono::duration_cast<chrono::microseconds>(end2 - start2);
cout<<"跨度为6的倍数的优化耗时：\t"<<duration2.count()<<"微秒"<<endl;
cout << "埃氏筛法\t";
auto start3 = chrono::system_clock::now();
Solution_3 s3;
cout << s3.countPrimes(n) << endl;
auto end3 = chrono::system_clock::now();
auto duration3 = chrono::duration_cast<chrono::microseconds>(end3 - start3);
cout<<"埃氏筛法耗时：\t"<<duration3.count()<<"微秒"<<endl;
cout << "埃氏筛法的优化\t";
auto start4 = chrono::system_clock::now();
Solution_4 s4;
cout << s4.countPrimes(n) << endl;
auto end4 = chrono::system_clock::now();
auto duration4 = chrono::duration_cast<chrono::microseconds>(end4 - start4);
cout<<"埃氏筛法的优化耗时：\t"<<duration4.count()<<"微秒"<<endl;
cout << "线性筛法\t";
auto start5 = chrono::system_clock::now();
Solution_5 s5;
cout << s5.countPrimes(n) << endl;
auto end5 = chrono::system_clock::now();
auto duration5 = chrono::duration_cast<chrono::microseconds>(end5 - start5);
cout<<"线性筛法耗时：\t"<<duration5.count()<<"微秒"<<endl;
return 0;
}测试结果
测试数据：n=867896
暴力法 68937
暴力法耗时： 84030微秒
跨度为6的倍数的优化 68937
跨度为6的倍数的优化耗时： 29138微秒
埃氏筛法 68937
埃氏筛法耗时： 739268微秒
埃氏筛法的优化 68937
埃氏筛法的优化耗时： 595306微秒
线性筛法 68937
线性筛法耗时： 39351微秒练习
https://leetcode.cn/problems/count-primes/
