Retos - 028: Factores primos

Nivel de dificultad aproximado (1 a 5): 1  

Enunciado del problema

El usuario introducirá un primer número entero positivo (de no más de 6 cifras) que indicará la cantidad de casos de prueba. Después seguirán varias líneas, cada una con un número entero positivo (de no más de 15 cifras). Para cada uno de esos casos de prueba, tu programa debe mostrar el número, un espacio en blanco, un signo de igualdad, otro espacio en blanco y los factores primos de ese número (repetidos si es el caso), cada uno de ellos con un espacio en blanco a continuación.

Cuidado: Como suele ocurrir en los retos de programación, hay que seguir exactamente las entradas y salidas (mira el ejemplo): NO es un programa interactivo, no debe avisar al usuario con frases como "Introduce un número" o "Dame un número". Sólo debe tomar datos numéricos enteros positivos de la entrada estándar, analizarlo y mostrar un resultado que también será una serie de números enteros. Del mismo modo, no debe existir ninguna pausa antes ni después de la ejecución del programa. No debes almacenar los datos de entrada en un array, sino dar el resultado para cada dato antes de leer la siguiente entrada.

Entradas y salidas de ejemplo 
Ejemplo de entrada
4
24
59
1234567890
987654321098765

Ejemplo de salida correspondiente
24 = 2 2 2 3 
59 = 59 
1234567890 = 2 3 3 5 3607 3803 
987654321098765 = 5 233 1279 662839679
Procedencia del reto

Original en: Recopilación de retos, Nacho Cabanes

Explicación

Una solución sencilla es probar todos los números desde 2 en adelante hasta llegar a N. Si es divisible, se reemplaza N por N/divisor y se vuelve a intentar; si no es divisible, se pasa a probar el siguiente divisor.

Dos optimizaciones muy simples pueden duplicar (cada una) la velocidad:

  • No hace falta probar todos hasta N, sino que se puede parar en N/2
  • No hace falta probar todos los divisores pares. En cuanto se ha comprobado el 2 y se ha pasado al 3, se puede seguir mirando sólo los divisores impares (sumando 2 al divisor en cada pasada)

En caso de números grandes y de muchos datos, se puede ganar mucha velocidad si se prueba a dividir sólo entre números primos, que se pueden calcular antes usando la "criba de Erastótenes" (en ese caso, la solución ya no es "de nivel 1")

Posibles errores:

  • No utilizar el primer dato (la cantidad de números a analizar) y dar por sentado que siempre van a ser "n" datos.
  • Mostrar información al pedir datos (por ejemplo "Dime la cantidad de datos").
  • Mostrar información de más junto con los resultados (por ejemplo "Los factores primos son...").
  • Mostrar mensajes que no se piden (por ejemplo, "Es primo")
  • No hacer la operación correctamente (por ejemplo, no probar varias veces cada posible divisor)
  • Usar números enteros en vez de enteros largos (con lo que algunos casos de prueba pueden desbordar, porque pueden ser números de 15 cifras)
Aporta tu solución

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 3 menos dos?
Lenguaje
Fuente:

Ejemplo de solución en COBOL 

*-------------------------------*
*LENGUAJE: COBOL RM 74.         *
*COMPILADO 12/Mar/2015.         *
*AUTOR SAM.                     *
*PARA: www.nachocabanes.com     *
*RETO: 28-FACTORES PRIMOS.      *
*Nota del recopilador:          *
*No probado                     *
*-------------------------------*
 
 IDENTIFICATION  DIVISION.
 PROGRAM-ID. FACTOR.
 AUTHOR.     SAM.
 ENVIRONMENT DIVISION.
 DATA            DIVISION.
 WORKING-STORAGE SECTION.
 01 WKS-CANTIDAD        PIC 9(06).
 01 WKS-DATO            PIC 9(15).
 01 WKS-I               PIC 9(06).
 01 WKS-J               PIC 9(06).
 01 WKS-REMAND          PIC 9(03).
 01 WKS-RESULT          PIC 9(15).
 01 TABLA.
    03 T-TABLA          OCCURS 100 TIMES.
       05 T-DATOS          PIC 9(15).
 
 PROCEDURE       DIVISION.
 INICIO.
 
    ACCEPT  WKS-CANTIDAD.
 
    PERFORM 1000-ACEPTA-DATOS
            VARYING WKS-I
            FROM 1 BY 1
            UNTIL WKS-I > WKS-CANTIDAD.
 
    PERFORM 1005-PROCESO-FACTOR
            VARYING WKS-I
            FROM 1 BY 1
            UNTIL WKS-I > WKS-CANTIDAD.
    STOP RUN.
 
 1000-ACEPTA-DATOS.
    ACCEPT T-DATOS(WKS-I).
 
 1005-PROCESO-FACTOR.
    MOVE T-DATOS(WKS-I) TO WKS-DATO.
    MOVE 99 TO WKS-RESULT.
    DISPLAY WKS-DATO " = ".
 
    PERFORM 1010-CALCULA-FACTOR
            VARYING WKS-J
            FROM 1 BY 1
            UNTIL WKS-RESULT = 1.
 
 1010-CALCULA-FACTOR.
    DIVIDE WKS-J INTO      WKS-DATO
                 GIVING    WKS-RESULT
                 REMAINDER WKS-REMAND.
 
    IF WKS-REMAND IS EQUAL TO ZEROES
       AND WKS-J NOT EQUAL TO 1
       DISPLAY WKS-J " "
       MOVE WKS-RESULT TO WKS-DATO
       MOVE 01 TO WKS-J.

Ejemplo de solución en C# 

// Solución al reto 028: Factores primos, C#
// Autor: César Hernández
// 13-Oct-2016
// Nota del recopilador: no es necesario usar un array para
// guardar los datos de entrada; se puede responder a cada dato
 
using System;
 
class _03_Factores_primos
{
	static void Main()
	{
		long[] casos = new long[Convert.ToInt32(Console.ReadLine())];
		for(int i = 0; i < casos.Length; i++)
			casos[i] = Convert.ToInt64(Console.ReadLine());
 
		for (int i = 0; i < casos.Length; i++)
			Factores_Primos(casos[i]);
	}
 
 
	static void Factores_Primos(long n)
	{
		int i = 2;
		string res = n + " = ";
		while(n != 1)
		{
			if (n % i == 0)
			{
				res += i + " ";
				n = (n / i);
			}
			else
				i++;
		}
		Console.WriteLine(res);
	}
}
 

Ejemplo de solución en Java 

// Solución al reto 028: Factores primos
// Autor: Jean Michael
// 19-Mar-2015
 
import java.util.Scanner;
 
public class reto028 {
        public static void calcularYMostrarFactoresPrimos(long n) {
                if (n == 1)
                        return;
                int i = 2;
                while (n % i != 0)
                        i++;
                System.out.print(i + " ");
                calcularYMostrarFactoresPrimos(n / i);
        }
 
        public static void main(String[] args) {
                Long option[];
                Scanner in = new Scanner(System.in);
                int c = Integer.parseInt(in.next());
                int i = 0;
                while (i < c) {
                        long n = Long.parseLong(in.next());
                        System.out.print(n + " = ");
                        calcularYMostrarFactoresPrimos(n);
                        System.out.println();
                        i++;
                }
        }
 
}

Ejemplo de solución en Pascal 

(* 
Solución al reto 028: Factores primos
Autor: José Antonio
18-Ene-2016
Nota del recopilador: almacena todos los datos en arrays, pero lo
esperable en un reto es trabajar dato a dato, mostrando cada
resultado inmediatamente
*)
 
PROGRAM reto28;
(*Programa que descompone en factores primos tantos numeros como
seleccione el usuario, este programa es la respuesta al reto Nº28
de la pag. web http://www.nachocabanes.com/retos/reto.php?n=028*)
VAR
  Numero:Int64;
  casos,i:Integer;
  datos: ARRAY [1..999999] OF Int64;
(*Declaramos funciones*)
 
(*Funcion que determina si un número es primo o no, si lo es devuelve
TRUE*)
FUNCTION es_primo (a:Int64):boolean;
VAR
  contador:Int64;
BEGIN
  contador:=1;
  es_primo:=True;
  (* 1 y 2 son primos*)
  IF ((a=1) OR (a=2)) THEN
  es_primo:=True
  ELSE
   BEGIN
   (*Todo número será primo si SOLO es divisible por uno y por si mismo
   probamos....*)
   REPEAT
    contador:=contador+1;
    IF (((a MOD contador)=0) AND (contador<a)) THEN
    es_primo:=False;
   UNTIL ((NOT es_primo) OR (contador=a));
  END;
END;
 
(*Función que obtiene el mínimo divisor primo mayor que 1 si el número es
distinto de 1. En caso de que el número sea 1 devuelve 1*)
FUNCTION min_prim_div(a:Int64):Int64;
VAR
  salir:boolean;
BEGIN
  (*Si el número introducido es 1 se devolverá 1*)
  IF (a=1) THEN
  min_prim_div:=1
  ELSE
  BEGIN
  (*Inicializar variables.El menor divisor primo posible mayor que uno es 2*)
  min_prim_div:=2;
  salir:=False;
 
  (*Si "a" no es divisible por 2 probamos uno por uno todos los impares ya que
  a partir de 2 todos los números primos posibles han de ser impares*)
  IF ((a MOD 2)<>0) THEN
  BEGIN
  min_prim_div:=3;
    REPEAT
     IF((a MOD min_prim_div)=0)AND(es_primo(min_prim_div)) THEN
     salir:=True
     ELSE
     min_prim_div:=min_prim_div+2;
    UNTIL (salir);
  END;
  END;
END;
 
(*Procedimiento que descompone un número en sus mínimos divisores primos y los muestra
por pantalla en el formato pedido*)
PROCEDURE descomponer_y_mostrar(a:Int64);
VAR
  factor:Int64;
BEGIN
  (*Primero mostramos lo que ya se conoce, es decir "a = ".*)
  Write(a,' = ');
  (*Ahora se irá descomponiendo "a" en factores primos y mostrandose en pantalla*)
  REPEAT
   factor:=min_prim_div(a);
   a:=a DIV factor;
   IF(a<>1) THEN
   Write(factor,' ')
   ELSE
   WriteLn(factor,' ');
  UNTIL (a=1) ;
END;
 
(*Programa principal*)
BEGIN
(*Leemos los datos por la entrada estándar*)
  ReadLn(casos);
  FOR i:=1 TO casos DO
   BEGIN
     ReadLn(numero);
     datos[i]:=numero;
   END;
 
  (*Calculamos las respuestas*)
  FOR i:=1 TO casos DO
   descomponer_y_mostrar(datos[i]);
END.