Daily Challenge #269 - Decompose n!

The goal of this challenge is to decompose n! (factorial n) into its prime factors. The function decomp(n) should return the decomposition of n! into its prime factors in increasing order of the primes, as a string. The factorial can be a very big number (4000! has 12674 digits, n will go from 300 to 4000).

Examples:
n = 12; decomp(12) -> "2^10 * 3^5 * 5^2 * 7 * 11"
since 12! is divisible by 2 ten times, by 3 five times, by 5 two times and by 7 and 11 only once.

n = 22; decomp(22) -> "2^19 * 3^9 * 5^4 * 7^3 * 11^2 * 13 * 17 * 19"
n = 25; decomp(25) -> 2^22 * 3^10 * 5^6 * 7^3 * 11^2 * 13 * 17 * 19 * 23

Prime numbers should be in increasing order. When the exponent of a prime is 1 don't write the exponent.

Tests:
decomp(17)
decomp(5)
decomp(22)
decomp(14)
decomp(25)

Good luck!

---

This challenge comes from g964 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Hayden Mankin]

Javascript

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(" * ");
}

[agtoever]

Using the extremely elegant solution described here.

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()

['']

bit.ly/3j2UpqA

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(" * ");

[Patryk Gronkiewicz]

You can check for divisors in [2;ceiling(sqrt(n))], that should be way faster for large n

[peter279k]

Here is my simple solution with PHP:

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;
}