/*
 * Sieve of Eratosthenes
 *
 * Generates array of prime numbers up to n
 * Runs in O(n log log n) time and O(n) space
 */
function genPrimesTo(n) {
  let flags = [];
  for (let i = 0; i <= n; i++) {
    if (i > 1) {
      flags.push(true);
	} else {
      flags.push(false);
    }
  }

  let prime = 2;
  let generatedPrimes = [];
  while (prime <= Math.sqrt(n)) {
    flag(flags, prime);
    prime = getNextPrime(flags, prime);
  }

  flags.forEach((val, i) => {
    if (val) {
      generatedPrimes.push(i);
    }
  });

  return generatedPrimes;
}

function flag(flags, prime) {
  for (let i = prime*prime; i < flags.length; i += prime) {
    flags[i] = false;
  }
}

function getNextPrime(flags, prime) {
  let next = prime + 1;
  while (next < flags.length && !flags[next]) {
    next += 1;
  }
  return next;
}

/*
 * Determines num's primality by checking divisibility of primes up to sqrt(num)
 */
function isPrime(num) {
  if (num <= 2) return true;
  const primes = genPrimesTo(Math.sqrt(num));
  for (let p of primes) {
    if (num % p === 0) return false;
  }
  return true;
}