Ehrlich screening method: Counting the number of prime numbers

The core idea of ​​the sieve method:When we find a prime number, then all multiples of this number less than n are definitely not prime numbers, while marking.

#include using namespace std;class Solution {public:bool isprime(int n){for (int i = 2; i*i <= n; i++){if (n % i == 0)return false;}return true;}int cout_prime(int n){int* tag = new int[n] {0};//0 represents a prime numberint count = 0;for (int i = 2; i < n; i++){if (tag[i]==0){count++;for (int j = i * i; j < n; j += i)//j+=i realizes the increment of i{tag[j] = 1;}}}return count;}};int main(){Solutions;int n = s.cout_prime(100);cout << n;return 0;}

In the above code, focus on this code:

for (int j = i * i; j < n; j += i)//j+=i realizes the increment of i{tag[j] = 1;}

The original version of this code is j = i*2; but since each i pair increments will be marked repeatedly, the code is optimized and incremented by i itself as a multiple each time to improve efficiency.