Simple JavaScript Solution


  • 1
    /**
     * @param {number} n
     * @return {number}
     */
    var countPrimes = function(n) {
        let flagArray = [],
            result = 0;
        for(let i = 2; i < n; i++){
            if(flagArray[i] === undefined){
                // is Primes
                flagArray[i] = 1;
                result++;
                // rm it's multiples
                let j = 2;
                while(i * j < n){
                    flagArray[i * j] = 0;
                    j++;
                }
            }
        }
        return result;
    };
    

  • 0
    D

    @fishguo321 Weird. What an elegant solution
    I thought Sieve of Eratosthenes is a better solution but implementing it in javascript always gives me MTE.

    Could you please elaborate on the time and space complexity of this also? Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.