primes.ts

/**
 * Implementation of the Sieve of Eratosthenes algorithm.
 *
 * @param limit An integer _n_ > 1
 * @returns All prime numbers from 2 through {@link limit}
 *
 * @see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 */
export function sieveOfEratosthenes(limit: number): number[] {
  if (!Number.isInteger(limit) || limit <= 1) {
    throw new Error('limit should be an integer greater than 1')
  }

  const maybePrime: boolean[] = new Array(limit + 1).fill(true)
  for (let i = 2; i * i <= limit; i++) {
    if (!maybePrime[i]) continue
    for (let j = i * i; j <= limit; j += i) {
      maybePrime[j] = false
    }
  }

  const primes: number[] = []
  for (let i = 2; i < maybePrime.length; i++) {
    if (maybePrime[i]) {
      primes.push(i)
    }
  }

  return primes
}

/**
 * Generator that yields primes.
 *
 * Inspired by https://gist.github.com/e-nikolov/cd94db0de2a6b70da144124ae93a6458
 */
export function* primeGenerator() {
  type NumberGen = Generator<number, void, any>

  function* filter(input: NumberGen, prime: number): NumberGen {
    while (true) {
      const { done, value } = input.next()
      if (done) break
      if (value % prime !== 0) yield value
    }
  }

  let chain: NumberGen = (function* () {
    let i = 2
    while (true) yield i++
  })()

  while (true) {
    const { done, value } = chain.next()
    if (done) break
    yield value
    chain = filter(chain, value)
  }
}

/**
 * @function isPrime
 * @description Determine if given number is prime.
 * @param {number} num - A natural number.
 * @return {boolean} - Whether the given number is prime.
 * @see https://en.wikipedia.org/wiki/Prime_number
 * @example isPrime(2) = false
 * @example isPrime(3) = true
 */
export const isPrime = (num: number): boolean => {
  // raise corresponding errors upon invalid inputs
  if (num <= 0 || !Number.isInteger(num)) {
    throw new Error('only natural numbers are supported')
  }

  // handle input being 1
  if (num === 1) return false

  // iterate from 2 to the square root of num to find a factor
  // return false upon finding a factor
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false
  }

  // if the entire loop runs without finding a factor, return true
  return true
}