Kata #1 - Prime Factors

A code kata is an exercise in programming which helps a programmer hone their skills through practice and repetition.

El kata Prime Factors es un kata de base matemática en la que escribimos un método que se romperá en una lista de sus factores primos. Esto significa que el método regresará el conjunto de uno o más números primos que al ser multiplicados resultará en el número inicial. En matemáticas, un número primo es un número natural mayor a 1 que tiene únicamente dos divisores distintos: él mismo y el 1.

Requisitos

Escribir un método generate que tomará un argumento entero y devolverá una colección de números enteros. Dicha lista contendrá los factores primos.

Ejemplos

  • generate(2) = [2]
  • generate(3) = [3]
  • generate(4) = [2,2]
  • generate(6) = [2,3]
  • generate(8) = [2,2,2]
  • generate(9) = [3,3]
  • generate(10)=[2,5]
  • generate(12) = [2,2,3]

Solución

Si quisieramos resolver éste problema en javascript tendríamos que crear una función para saber si un número es primo o no. La lógica detrás de un número primo radica en que todos los números pueden ser divididos entre 1 y el mismo, por lo que tendríamos que buscar si un número entre ese rango puede dividir al número que queremos validar:

var isPrime = function (num){
    if(num == 2){ // 2 is prime
        return true;
    }else if(num % 2 === 0) { // 2 is the only pair prime
        return false;
    }

    for (var i = 2; i < Math.sqrt(num); i++) {
        if(num % i === 0){
            return false;
        }
    }

    return true;
};

El primer if-else nos ayudará a a descartar cualquier número que sea par, y regresará true con el número 2 ya que éste es el único número par primo que existe. Gracias al algoritmo de la criba de Eratóstenes podemos reducir el rango de números de nuestro ciclo hasta la raíz cuadrada del número a validar.

Pensándolo bien, no necesitamos éste método. Tenemos la respuesta en la definición de un número primo. Nuestro método generate toma un número y regresa un Array con el múltiplo de los factores de número primos, los cuales a su vez, son aquellos que al dividirse se obtiene un residuo de 0.

Llamemos n a nuestro número que querramos pasar como argumento al método generate. Si n = 100, entonces dividamos entre 2 y busquemos residuo, si éste es 0, volvamos a dividir hasta que sea diferente. Una vez diferente, sigamos con el siguiente número y así hasta que n == 1.

Ejemplo:

  • 100 / 2 = 50
  • 50 / 2 = 25
  • 25 / 2 Hay residuo
  • 25 / 3 Hay residuo
  • 25 / 4 Hay residuo
  • 25 / 5 = 5
  • 5 / 5 = 1

Nuestro resultado sería [2,2,5,5] y sin la necesidad de usar la función isPrime. Por lo que nuestro código final sería:

function generate(n) {
  let primes = [];
  
  for(let i = 2; n > 1; i++){
    while(n % i == 0){
      primes.push(i);
      n /= i;
    }
  }
  
  return primes;
}

console.log(generate(100));

JS Bin on jsbin.com

Recuerden que si ya tienen un algoritmo para resolver un problema, no olviden preguntarse: ¿Se puede mejorar?

Nos leemos!!!