// sieve of eratosthenes
const primesBelow = (n: number): number[] => {
  const primes: number[] = [];
  const isPrime: boolean[] = Array(n).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i < n; i++) {
    if (isPrime[i]) {
      primes.push(i);
      for (let j = i * i; j < n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  return primes;
}

// prime factorization using trial division
const primeFactors = (n: number, primesList: number[]): number[] => {
  const factors: number[] = [];
  const sqrtN = Math.sqrt(n);
  const primes = [...primesList];
  let currPrime = primes.shift() as number;
  while (currPrime <= sqrtN) {
    if (n % currPrime === 0) {
      factors.push(currPrime);
      n /= currPrime;
    } else {
      currPrime = primes.shift() as number;
    }
  }

  if (n > 1) {
    factors.push(n);
  }

  return factors;
}

const generatePrimeFactors = (upper: number): number[] => {
  // this stores the number of times a number is marked as a prime factor
  const factors: number[] = Array(upper + 1).fill(0);

  for (let p = 2; p <= upper; p++) {
    if (factors[p] === 0) {
      // p is prime
      // mark all multiples of p
      for (let j = p; j <= upper; j += p) {
        // also mark all multiples of p^2, p^3, ...
        for(let k = j; k <= upper; k *= p) {
          factors[k]++;
        }
      }
    }
  }

  return factors;
}

// create static class which can be called a single time for a very large range
export class KPrimes {
  private static limit = 10001000;
  private static primeFactors = generatePrimeFactors(KPrimes.limit);

  public static countKprimes(k: number, start: number, nd: number): number[] {
    if(nd > KPrimes.limit) {
      throw new Error(`nd: ${nd} is greater than the limit: ${KPrimes.limit}`);
    }
    // filter out the numbers that have k prime factors
    const result = [];
    for (let i = start; i <= nd; i++) {
      if (KPrimes.primeFactors[i] === k) {
        result.push(i);
      }
    }

    return result;
  }
}

// using modified sieve of eratosthenes
export const countKprimes = (k: number, start: number, nd: number): number[] => {
  return KPrimes.countKprimes(k, start, nd);
}

export const puzzle = (s: number): number => {
  const onePrimes = countKprimes(1, 0, s);
  const threePrimes = countKprimes(3, 0, s);
  const sevenPrimes = countKprimes(7, 0, s);

  let count = 0;

  onePrimes.forEach(onePrime => {
    threePrimes.forEach(threePrime => {
      sevenPrimes.forEach(sevenPrime => {
        if (onePrime + threePrime + sevenPrime === s) {
          count++;
        }
      });
    });
  });

  return count;
}