• Empleos
  • Sobre nosotros
  • profesionales
    • Inicio
    • Empleos
    • Cursos y retos
    • Preguntas
    • Profesores
  • empresas
    • Inicio
    • Publicar vacante
    • Nuestro proceso
    • Precios
    • Pruebas Online
    • Nómina
    • Blog
    • Comercial
    • Calculadora de salario

0

110
Vistas
Question regarding Legendre's formula and recursion?

I am currently learning about the Legendre's formula. Thus far, I was able to solve the algorithm with the following approach:

const legendre = (p,n,res=0) => Array.from({length:n},(_,i) => res+=Math.floor(n/p**++i)) && res;

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

However, I just couldn't quite get over the hump recursively. This is what I have so far:

const legendre = (p,n,i=1,res=0) => p > n ? res : res + legendre(p**i,n,i+1,Math.floor(n/p**i))

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 99 
console.log(legendre(3,60)); // 26
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 300

As you can see, most of the results are incorrect. Am I on the right track? Can someone kindly point me in the right direction or show me what I'm doing wrong? Any feedback will be greatly appreciated. Million thanks in advance :)

almost 3 years ago · Juan Pablo Isaza
1 Respuestas
Responde la pregunta

0

I started by converting your first code into a normal function:

const legendre = (p, n) => {
  let res = 0;
  for (let i = 1; i <= n; i++) {
    res += Math.floor(n/p**i);
  }
  return res;
}

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

and converted that into a recursive function:

const legendre = (p, n, i=1, res=0) => {
  // base case -> done
  if (i > n) return res + Math.floor(n/p**i);
  return legendre(p, n, i+1, res + Math.floor(n/p**i));
}

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

and that can be made into a oneliner like this:

const legendre = (p,n,i=1,res=0) => i > n ? res + Math.floor(n/p**i) : legendre(p,n,i+1,res +Math.floor(n/p**i))

console.log(legendre(5,90)); // 21
console.log(legendre(2,130)); // 128
console.log(legendre(3,60)); // 28
console.log(legendre(9,5)); // 0
console.log(legendre(5,1250)); // 312

I haven't studied this algorithm and these answers are just based off your first code snippet and your test cases.

almost 3 years ago · Juan Pablo Isaza Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Nuestro proceso Comercial
Legal
Términos y condiciones Política de privacidad
© 2025 PeakU Inc. All Rights Reserved.

Andres GPT

Recomiéndame algunas ofertas
Necesito ayuda