埃拉托斯特尼筛法的时间复杂度

1. Overview

In this tutorial, we’ll discuss the Sieve of Eratosthenes algorithm. We’ll also present the time complexity analysis of the algorithm.

2. Theoretic Idea

Given a number , we need to find all the prime numbers up to the input integer .

The Sieve of Eratosthenes algorithm is simple, but one of the most efficient ways to find them in a segment [1, N] . The first step of the algorithm is to write down all the numbers from $\mathbf{2}$ to the input number $\mathbf{N}$ .

For any given input number greater than $\mathsf{2}$ , the first prime would always be $\mathsf{2}$ . So we’ll create a list of consecutive integers from $\mathsf{2}$ to a specified input integer . At this point, we found the first prime number. Next, we’ll remove all the integers from our list, which are the multiples of $\mathbf{2}$ (since $\mathsf{2}$ is the first prime number).

We’ll continue choosing the next prime numbers and remove the multiples of the current prime number from our list until the current prime number is less than or equal to $\mathbf{\sqrt{N}}$ . Finally, all the integers which will remain in our list are our prime numbers.

3. Pseudocode

We discussed the steps of the Sieve of Eratosthenes algorithm, let’s see the pseudocode now:

algorithm SievePrime(N)
    // INPUT
    //    N = a positive integer > 2
    // OUTPUT
    //    All the prime numbers < N
    
    L <- array of of size N filled with ones
    result <- empty array
    
    for k <- 2 to sqrt(N):
        if L[k] = 1:
            j = k * k
            while j <= N:
                L[j] <- 0
                j <- j + k
    
    for s <- 1 to N:
        if L[s] = 1:
            result.append(s)
    
    return result

Here we take a number as an input and create an array of size . The index of the array represents the numbers, and the values inside the array denotes whether it’s a prime number or not. If the value inside is $\mathsf{0}$ , its a composite number. Similarly, if the value inside is $\mathsf{1}$ , it’s a prime number.

We know that $\mathsf{1}$ is not a prime number, so we start the algorithm by initializing L[1] to $\mathsf{0}$ and the rest of the indices to $\mathsf{1}$ . In each iteration, we set a loop value and check whether it’s a composite or prime number. If it’s a prime number, we remove all the integers from our list which are the multiples of that prime number by assigning them $\mathsf{0}$ .

We’ll run the algorithm until the current loop value is less than or equal to $\sqrt{N}$ . Finally, we return all the indices whose value is $\mathsf{1}$ .

4. Example

Let’s take N = 30 . The first step is to create a list of size $\mathsf{30}$ and assign the first index to $\mathsf{0}$ and the rest with $\mathsf{1}$ :

1-1

Now we’ll start the iteration. Initially, we set loop value to $\mathsf{2}$ and check the index of the array if it contains the value $\mathsf{1}$ or not. If the index $\mathsf{2}$ in contains $\mathsf{1}$ , we assign $\mathsf{0}$ to all the indices, which are the multiples of current loop value:

by 2-1

Next, we’ll set the value of the loop to $\mathsf{3}$ , and continue the same process:

by 3-2

The next loop value would be $\mathsf{4}$ , but as we can see, its value is $\mathsf{0}$ . So we’ll go to the next index that’s $\mathsf{5}$ and repeat the same process:

by 5-1

Our next prime would be $\mathsf{7}$ , but according to the algorithm, we’ll stop when the current prime number is less than or equal to $\sqrt{N}$ . Here is $\mathsf{30}$ , therefore $\sqrt{30}$ is $\mathsf{5.477}$ . So we’ll not continue with the next prime number and terminate the algorithm. The algorithm returns the indices which have value $\mathsf{1}$ , and these are all prime numbers:

[L = [2, 3, 5, 7 , 11, 13, 17, 19, 23, 29]]

5. Time Complexity

The core part of this algorithm is to mark the composite numbers and remove them from the list by assigning $\mathsf{0}$ . Now to mark a composite number and assign the value $\mathsf{0}$ to it takes $\mathcal{O}(1)$ time. The real complexity of this algorithm lies in the number of times the loops run to mark the composite numbers.

In order to remove the composite numbers, we assign the value $\mathsf{0}$ to the multiples of the current prime number in . Now let’s assume our current prime number is $\mathsf{2}$ . In the first iteration, we’ll mark $\frac{N}{2}$ elements. Like this, when our current prime number is $\mathsf{3}$ , we assign $\mathsf{0}$ to $\frac{N}{3}$ composite numbers. The total number times we runs the loop would be equal to:

$[\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \frac{N}{7} + .......]$

Let’s solve this equation:

$[N*(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + ....... )]$

Using Harmonic Progression of the sum of primes, it can be proved that:

$[(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + ....... ) = log(log(N))]$

Therefore, total time complexity of the Sieve of Eratosthenes algorithm would be $\mathbf{\mathcal{O}(Nlog(log(N)))}$ .

6. Conclusion

In this tutorial, we’ve discussed the Sieve of Eratosthenes algorithm in detail. We presented the pseudocode of the algorithm and analyzed the time complexity.

Persistence

REST

Security