Retos - 028: Factores primos

Nivel de dificultad aproximado (1 a 5): 1  

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.

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 

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)

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 2 más 3?
Lenguaje
Fuente:

*-------------------------------*
*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.

// 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++;
                }
        }
 
}