Descomposición en factores primos

De ChuWiki
Revisión del 23:28 10 nov 2007 de Chudiang (Discusión | contribuciones)

(dif) ← Revisión anterior | Revisión actual (dif) | Revisión siguiente → (dif)
Saltar a: navegación, buscar

Vamos a hacer un pequeño programa en Java para descomponer un número en factores primos. El algoritmo utilizado no es el mejor ni el más eficiente, pero para hacer un pequeño ejemplo en Java nos valdrá.

Para la descomposición, empezaremos con un primer factor=2. Mientras el número sea divisble por este factor, lo dividiremos y volveremos a probar con el cociente. Cuando el número no sea divisible por ese factor, incrementaremos el factor en uno. Aquí tenemos una mejora que no haremos. Una vez probado el factor 2, pasaremos al 3. A partir de aquí ya no tiene sentido probar los factores pares, como el 4. A partir de 3 podríamos incrementar de 2 en 2.

Para probar si el número es divisible por el factor, usaremos la operación módulo, que en Java es %. Si valor%factor es cero, quiere decir que valor es divisible por factor.

El código de ejemplo es el siguiente

/*
 * Ejemplo de descomposición en factores primos.
 */
package com.chuidiang.metodos_numericos;

import java.util.LinkedList;

/**
 * Descomposición en factores primos.
 * @author chuidiang
 */
public class FactoresPrimos {
	/**
	 * Un bucle de 2 a 100 para ir descomponiendo todos esos números en factores primos.
	 * Escribe todos ellos con su descomposición por pantalla.
	 * @param args
	 */
	public static void main(String[] args) {
		for (int i=2;i<=100;i++)
		{
		   LinkedList<Integer> factores = FactoresPrimos.descomponEnFactoresPrimos(i);
		   System.out.print(i+"=");
		   for (Integer factor: factores)
		   {
			   System.out.print(factor);
			   
			   // Si no es el último, escribe el signo *
			   if (factor != factores.getLast())
				   System.out.print("*");
		   }
		   System.out.println();
		}
	}

	/**
	 * Se le pasa un valor entero superior a 1 y devuelve una lista de factores primos
	 * en los que ha descompuesto el número. 
	 * @param valor Número de descomponer
	 * @return Lista de factores primos.
	 */
	public static LinkedList<Integer> descomponEnFactoresPrimos(int valor)
	{
		assert valor>1;
		
		// Se empieza probando como posible factor primo el 2.
		int factor = 2;
		LinkedList<Integer> factores=new LinkedList<Integer>();
		
		while (factor <= valor)
		{
			// Mientras es divisible, se añade el factor a la lista de factores primos
			// y se realiza la división.
			while (valor % factor == 0 )
			{
				factores.add(new Integer(factor));
				valor = valor/factor;
			}
			
			// Si no es divisible, se pasa al posible siguiente factor.
			factor++;
		}
		
		return factores;
	}
}