DEV Community

Discussion on: Daily Challenge #269 - Decompose n!

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