[Note] Sieve of Eratosthenes

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm used to find all prime numbers up to a specified integer. It is one of the most efficient ways to find all primes smaller than a given number, especially when that number is large.

Question

Given a number N, count how many primes or composites there are in the number from 0 to N.

Idea

To judge a prime number is to judge whether the number has any other numbers that can be divisible besides 1 and itself. If not, it is an integer. The simplest idea is to judge all numbers smaller than yourself, which will increase a lot of calculation time and the complexity will be O(N^2). Sieve of Eratosthenes is an algorithm that will reduce its computational complexity.

The idea of the Sieve of Eratosthenes algorithm is to set the multiples of known prime numbers as sums less than a given number. When the prime numbers from 1 to  logN \ log{N}\ have been judged, all the prime numbers can be found. of prime numbers.

When a prime number is found, all numbers less than N will be set as sums starting from  N2 \ N^2\ . Why start with N2 \N^2\ ? Because  N∗x \ N * x\ all  x \ x\ less than  N \ N\ will be judged before the previous prime number, so it only needs to start from  N2 \ N^2\ .

Code

  • Space Complexity:  O(N) \ O(N)\
  • Time Complexity:  O(NloglogN) \ O(\sqrt{N}loglogN)\
    •  N \ \sqrt{N}\ : for outer loop
    •  loglogN \ loglogN\ : for inner loop

For a proof of time complexity, please refer to detail.

int countPrime (int n) {
    vector<int> prime(n + 1, 1);
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i)
                prime[j] = 0;
        }
    }
    int primeCount = 0;
    for (int i = 2; i < n; i++) {
        if (prime[i])
            primeCount++;
    }
    return primeCount;
}

Practice

LeetCode 204. Count Primes

Algorithms