Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Descomposición en factores primos

Descompón un número en sus factores primos, ordenados de menor a mayor y con repetición.

Lo que aprenderás

  • Dividir entre cada factor tantas veces como aparezca
  • Detener la división de prueba cuando d × d supere lo que queda
  • Reconocer que un resto mayor que 1 es un factor primo

Problema

Ver original (inglés)

Todo entero mayor que 1 se puede escribir como producto de primos de una única manera, sin contar el orden de los factores (el teorema fundamental de la aritmética). Por ejemplo, 360 = 2 × 2 × 2 × 3 × 3 × 5. Encontrar esa lista se llama descomposición en factores primos (o factorización prima).

Implementa prime_factorization(n).

n puede llegar a 10^12, así que el método clásico es la división de prueba: divide entre 2 mientras se pueda, luego entre 3, y así sucesivamente. Solo necesitas probar divisores d mientras d × d ≤ la parte de n que aún queda; lo que quede al final por encima de 1 es primo. Así el trabajo se limita a unos √n ≈ 10^6 pasos, incluso cuando n es un primo grande o el producto de dos primos grandes.

Entrada

n: el número que hay que factorizar.

Salida

Devuelve los factores primos de n en orden ascendente, repitiendo cada primo tantas veces como divida a n, de modo que el producto de la lista sea n. Para n = 1, devuelve una lista vacía. Si n es primo, la lista tiene un único elemento, n.

Restricciones

1 ≤ n ≤ 10^12

Ejemplos

Ejemplo 1
Entrada:
n = 360

Salida esperada:
expected = [2, 2, 2, 3, 3, 5]
Entrada:
long long n = 360;

Salida esperada:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
Entrada:
long n = 360;

Salida esperada:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};

Explicación

360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5, así que la respuesta es [2, 2, 2, 3, 3, 5].

Ejemplo 2
Entrada:
n = 97

Salida esperada:
expected = [97]
Entrada:
long long n = 97;

Salida esperada:
std::vector<long long> expected = {97};
Entrada:
long n = 97;

Salida esperada:
long[] expected = new long[] {97};

Explicación

Ningún primo hasta √97 ≈ 9.8 (2, 3, 5, 7) divide a 97, así que es primo y la respuesta es [97].

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Divide entre 2 mientras se pueda y luego pasa a 3, 5, 7, etc.

Pista 2

Reduce n cada vez que encuentres un factor y compara d × d con el n reducido.

Pista 3

Si después del bucle queda algo mayor que 1, es el factor primo más grande.

Complejidad esperada

tiempo O(√n), espacio extra O(log n) para el resultado

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.