the Sieve of Eratothenes and binary search

Today, let's introduce two famous algorithms -- the Sieve of Eratosthenes and binary Search.

Before we start, we'll introduce a notation that will calculate how fast an algorithm runs -- the Big O Notation.

Consider an array of n elements. Sequential search will check every element before we find the element wanted. Therefore, it takes about n operations. Using the Big O Notation, it is O(n). The Big O Notation shows how the algorithm's running time goes up as the input goes up.

 

For example, there's a piece of code below:

def a(n: int) -> int:
    return 1

The time it takes does not change with n. We call the time complexity of this function O(1).

 

Another example:

def b(n: int) -> list:
    array = []
    for i in range(1, n+1):
        arrray.append(i)
    return array

 

The time this function takes is theoretically proportional to n. We call the time complexity of this function O(n).

 

the Sieve of Eratosthenes

The Sieve of Eratosthenes is introduced by Greek mathematician Eratothenes. It is used to count prime numbers in a specific range.

Steps:

1. Generate an array of length n

2. Mark all the elements prime for the time being.

3. Delete 1 as 1 is neither prime nor composite.

4. Read the minimum number of the array which is 2. Keep 2 and delete all the multiples of 2.

5. Read the minimum number of the array which is 3. Keep 3 and delete all the multiples of 3.

6. ...

7. Repeat the steps above until all the numbers are marked to be kept or to be deleted.

Time complexity: O(n log log n)

Code (language: Go):

func countPrimes(n int) (cnt int) {
    flags := make([]bool, n+1) // step 1
    for i := 2; i <= n; i++ {
        flags[i] = true // step 2
    }
    // the loop starts from 2 which represents step 3.
    for i := 2; i*i <= n; i++ {
        if flags[i] {
            // if the current number is marked to be kept,
            // then traverse all the multiples of current number
            // as i * 2 can be devided by 2, i * 3 can be devided by 3, ...
            // so all the multiples of i which is smaller than i * i is marked to be deleted.
            for j := i; j*i <= n; j += 1 {
                if flags[j*i] { // if a multiple of the current number has been marked to be deleted, no processing will be performed.
                    flags[j*i] = false // mark the multiple of the current number to be deleted
                }
            }
        }
    }
    // count how many prime numbers in all
    for i := range flags {
        if flags[i] {
            cnt++
        }
    }
    // return the result
    return
}

Give n the value of 100,000,000 and run the program.

It takes the Sieve of Eratosthenes 0.8 seconds. And there are 5,761,1455 prime numbers smaller than 100,000,000.

For comparison, I wrote another version in the traditional way. The main idea of the traditional way of counting prime numbers is to judge if each number is prime. It takes 2600 seconds which is about 43 minutes. The Sieve of Eratosthenes is about 3000 times faster than the old way, which shows its high efficiency.

 

Binary Search

This algorithm is used to find the index of an element in a sorted array.

First, let's consider an array of [1, 2, 4, 7, 9, 10].

How to find the index(or you can call it position) of 9?

It sounds simple. Start from 1 and compare one by one until we find it. The sequential search does work. The time complexity of sequential search is O(n). In this case, it will take 5 comparisons.

But, the time complexity of binary search is O(log n).

Steps:

1. Find the element in the middle of the array. In this case, the middle element is 4.

2. Compare 4 and 9. Note that 9 is greater than 4.

3. Reduce the array to [4, 7, 9, 10].

4. Find the middle element 7.

5. Note that 9 is greater than 7.

6. Reduce the array to [9, 10]

7. Find the middle element 9.

8. Note that 9 equals 9. The operation completes.

It takes 3 comparisons.

The number of comparisons is not much smaller, right?

Then consider an array of 100,000,000 elements. In the most 'unfortunate' case, it will take the sequential search 100,000,000 comparisons to find the element we want. But it will only take binary search 20 comparisons. That's much faster.

Code (language: Go):

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for right > left {
        // The line below is the same as `mid := (left + right) / 2`
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if nums[left] != target {
        return -1
    }
    return left
}