We can write a function that finds all the prime numbers less than \texttt{n} using the sieve of Eratosthenes:

Start
    Put numbers from 2 to n in a sieve (array)
    Repeat
        Select and remove from the sieve the smallest integer
        this integer is prime
        Remove its multiples
    Until sieve is empty
End

void primeN(int Prime[], int N)
{
    int Prime[Nmax], Status[Nmax], i, j, k, L, m, end;
    i=2;
    while(i<N)
    {
        Status[i]=1;
        i++;
    }

    k=1;
    Prime[k]=1;
    end=0;
    i=2;
    while(i<=N && end==0)
    {
        // find the smallest
        j=i;
        while(j<=N && Status[j]==0)
            j=j+1;
        if(j<=N)
        {
            //Save the prime number
            k=k+1;
            Prime[k]=j;
            L=1;
            m=L*j;
            //remove its multiples
            while(m<=N)
            {
                Status[m]=0;
                L++;
                m=L*j;
            }
            i=j+1;
        }
        else
            end=1;
    }
}

Study the complexity of the above function.

Hint: \(\sum_{p \leq n, p\ prime} \frac{1}{p} \in O(\log(\log n))\)

Difficulty level
This exercise is mostly suitable for students 
O(N*log(log(N)))
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Removing a sequence of 3 characters from a string