// // Description:

// // Count the number of prime numbers less than a non-negative number, n.

// Hint:

// Let's start with a isPrime function. To determine if a number is prime,
// we need to check if it is not divisible by any number less than n.
// The runtime complexity of isPrime function would be O(n)
// and hence counting the total prime numbers up to n would be O(n2). Could we do better?

// As we know the number must not be divisible by any number > n / 2,
// we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?

// Let's write down all of 12's factors:

// 2 × 6 = 12
// 3 × 4 = 12
// 4 × 3 = 12
// 6 × 2 = 12
// As you can see, calculations of 4 × 3 and 6 × 2 are not necessary.
// Therefore, we only need to consider factors up to √n because,
// if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.

// Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?

// The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n.
// But don't let that name scare you, I promise that the concept is surprisingly simple.


// We start off with a table of n numbers. Let's look at the first number, 2.
// We know all multiples of 2 must not be primes, so we mark them off as non-primes.

// Then we look at the next number, 3.
// Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well.

// Now we look at the next number, 4, which was already marked off. What does this tell you?
// Should you mark off all multiples of 4 as well?
// 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2
// and were already marked off.

// So we can skip 4 immediately and go to the next number, 5.
// Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off.
// There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
// In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2,
// similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p,
// we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ...
// Now what should be the terminating loop condition?

// It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient.
// Do you still remember Hint #3?

// Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off.
// When the loop terminates, all the numbers in the table that are non-marked are prime.

// The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n).
// For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.


// Sieve of Eratosthenes solution

var countPrimes = function(n) {
    var isPrime = [false, false];
    var floorSqrtN = Math.floor (Math.sqrt(n) );
    var i = 2;
    while(i <= floorSqrtN ){
        if( isPrime[i] !== false) {
            for( var j = i * i; j <= n; j += i ){
                isPrime[j] = false;
            }
        }
        i++;
    }
    for( i = 0, count; i < n; i++ ){
        if( isPrime[i] !== false ) count++;
    }
    return count;
};

// -----------------------------------------------

// create an array called primes
// loop through primes array to store each value as true until proven false
// create var limit to store the square root of the value given
// loop through sqrt of the value starting from 2.
    // if the current element is true we check its multiples
        // loop through the current numbers multiples and mark them as false since they are not primes
// once we've check all numbers up to our limit we loop though our primes array
    // increment our cout variable for every number that is marked as true, as it is prime
// return count

var countPrimes = function(value) { // 222 ms runtime
    var primes = [];
    for(var i = 2; i < value; i++) {
        primes[i] = true;
    }
    var limit = Math.sqrt(value);
    for(i = 2; i < limit; i++) {
        if(primes[i] === true) {
            for(var j = i * i; j < value; j += i) {
                primes[j] = false;
            }
        }
    }
    for(i = 2, count = 0; i < value; i++) {
        if(primes[i] === true) count++;
    }
    return count;
};

@@ -4246,33 +4246,63 @@
  %3C value; i++) %7B
+ // =%3E %5Btrue, true, .... true%5D
 %0A
-
         primes%5Bi
@@ -4420,60 +4420,180 @@
 e) %7B
-%0A            for(var j = i * i; j %3C value; j += i) %7B
+ // no need to check multiples of numbers that are not primes%0A            for(var j = i * i; j %3C value; j += i) %7B // check off multiples because we know they wont be primes
 %0A   

add notes