0

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);`
Pointy
  • 405,095
  • 59
  • 585
  • 614
WilliamG
  • 31
  • 5
  • You can do much better than that. When you find a prime, you don't have to check modulus values, you can simply compute the multiples of that prime by iterating through values incrementing by the value of the new prime. So when your code finds 5, it can set 10, 15, 20, 25, etc without any modulus operations. Similarly, compute the square root *outside* the loop header. – Pointy Jan 27 '23 at 23:46
  • Also: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity – Matt Johnson-Pint Jan 27 '23 at 23:48

0 Answers0