DEV Community

Cover image for Daily Challenge #269 - Decompose n!
dev.to staff
dev.to staff

Posted on

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 yo+challenge@dev.to with your suggestions!

Top comments (5)

Collapse
 
dry profile image
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(" * ");
}
Collapse
 
agtoever profile image
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()
Collapse
 
_bkeren profile image
'' • Edited

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


Collapse
 
pgronkievitz profile image
Patryk Gronkiewicz

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

Collapse
 
peter279k profile image
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;
}