Daily Challenge #269 - Decompose n!

function decomp(n) {
  let primes = new Array(n + 1).fill(true);
  for(let i = 2; i <= n; i++) {
    if (primes[i]) {
      for(let j = i + i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  primes = Object.entries(primes).filter(i=>i[1]).splice(2).map(i=>i[0]);

  let factorization = {}

  for(let i = 0; i < primes.length; i++) {
    let cnt = 0;
    for(let cur = Math.floor(n / primes[i]); cur >= 1; cur = Math.floor(cur / primes[i])) {
      cnt += cur;
    }
    factorization[primes[i]] = cnt;
  }

  return Object.entries(factorization).map(i => i[0] + (i[1] > 1 ? "^" + i[1] : "")).join(" * ");
}

from math import log, factorial


def sundaram3(max_n):
    """ Returns a list of all primes under max_n """
    numbers = list(range(3, max_n + 1, 2))
    half = (max_n) // 2
    initial = 4
    for step in range(3, max_n + 1, 2):
        for i in range(initial, half, step):
            numbers[i - 1] = 0
        initial += 2 * (step + 1)
        if initial > half:
            return [2] + list([_f for _f in numbers if _f])


def decomp(n):
    """ Performs factorial prime factorization of n.
        Returns a factor: exponent dictionary.
    """
    return {p: sum(n // p**k for k in range(1, int(log(n, p)) + 1))
            for p in sundaram3(n + 1)}


def main():
    testcases = [5, 12, 14, 17, 22, 25]
    for case in testcases:
        factors_str = ' * '.join(f'{b}^{p}' for b, p in decomp(case).items())
        print(f"{case}! = {factors_str}")


if __name__ == '__main__':
    main()

const isPrime = (number) => {
  let list = [...Array(Math.floor(number ** 0.5)).keys()]
    .map((x) => x + 1)
    .slice(1);
  return !list.some((n) => number % n === 0);
};

const findPrimes = (number) =>
  [...Array(number + 1).keys()].slice(2).filter((n) => isPrime(n));

const factorize = (number, prime) => {
  let result = 0;
  for (let i = number; i >= prime; ) {
    let div = Math.floor(i / prime);
    result += div;
    i = div;
  }

  return result > 1 ? `${prime}^${result}` : `${prime}`;
};

const decomp = (n) =>
  findPrimes(n)
    .map((prime) => factorize(n, prime))
    .join(" * ");

function decomp($n) {
  $result = [];
  $index = 2;

  for($index=2; $index <= $n; $index++) {
    $number = $index;
    $numberIndex = 2;
    if (isPrime($number) === false) {
      while (isPrime($number) === false) {
        if ($number % $numberIndex === 0) {
          if (array_key_exists((string)$numberIndex, $result) === true) {
            $result[(string)$numberIndex] += 1;
          } else {
            $result[(string)$numberIndex] = 1;
          }

          $number = (int)($number / $numberIndex);
        } else {
          $numberIndex += 1;
        }
      }

      if (array_key_exists((string)$number, $result)) {
         $result[(string)$number] += 1;
      } else {
         $result[(string)$number] = 1;
      }
    }

    if (isPrime($index) === true) {
      if (array_key_exists((string)$index, $result)) {
        $result[(string)$index] += 1;
      } else {
        $result[(string)$index] = 1;
      }
    }
  }

  $answer = "";
  foreach($result as $key => $value) {
    if ($key === 1) {
      continue;
    }
    if($value === 1) {
      $answer .= $key . " * ";
      continue;
    }
    $answer .= $key . "^" . $value . " * ";
  }

  return substr($answer, 0, -3);
}

function isPrime($n) {
  $count = ceil(sqrt($n));
  for($index=2; $index<=$count; $index++) {
    if ($n % $index === 0) {
      return false;
    }
  }

  return true;
}