What is the big O notation of the Sieve of Erastothenes algorithm?

26 Views Asked by At

I included my code solution for the Sieve of Erastothenes algorithm. I've just been introduced to big O notation and I am trying to figure out the time complexity of my algorithm.

function sieve(n)
{
    const numberList = [false, false]; //set element 0 and 1 as false because 0 and 1 are not primes

    for(let i = 2; i <= n; i++) 
        numberList[i] = true;

    for(let i = 2; i <= Math.sqrt(n); i++)
        {
            if(numberList[i] === false)
                continue;
            
            for(let j = i + 1; j <= n; j++)
            {
                if(j % i === 0)
                    numberList[j] = false;
            }
        }

    const results = [];

    //add to results array the value i if the position at i in numberList is true. This is to gather together all the prime numbers
    for(let i = 2; i <= n; i++)
    {
        if(numberList[i] === true)
            results.push(i);
    }

    return results; 
}

const primeList = sieve(100);
console.log(`From 1 to 100, there are ${primeList.length} prime numbers`, primeList);`
0

There are 0 best solutions below