[Java] Obtener factores primos de un Número

  • 4 Respuestas
  • 4394 Vistas

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado hackmin

  • *
  • Underc0der
  • Mensajes: 67
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil

[Java] Obtener factores primos de un Número

  • en: Febrero 21, 2015, 09:56:24 am
Ejemplo los factores primos de:  600851475143 son:

Código: You are not allowed to view links. Register or Login
1
71
839
1471
6857
59569
104441
486847
1234169
5753023
10086647
87625999
408464633
716151937
8462696833

y seguro que falta una mas, por que al ser un numero tan grande lo quite para no esperar hasta el final.

Código: Java
  1. import java.util.*;
  2. public class Ejercicios {
  3.  
  4.    public static void main(You are not allowed to view links. Register or Login[] args) {
  5.      
  6.    
  7.    
  8.    
  9.    
  10.     Scanner cin = new Scanner(You are not allowed to view links. Register or Login.in);
  11.     long GetPrimo = cin.nextLong();
  12.    int Contador = 0;
  13.    
  14.    
  15.    for(long i = 1; i <= GetPrimo;i++){
  16.      
  17.       if(GetPrimo % i == 0){
  18.          You are not allowed to view links. Register or Login.out.println(i);
  19.       }
  20.    }
  21.      
  22.    }
  23.    
  24.    }

Nivel de dificultad: Básico
« Última modificación: Marzo 12, 2015, 10:01:05 am por Expermicid »

Desconectado Yavi

  • *
  • Underc0der
  • Mensajes: 166
  • Actividad:
    0%
  • Reputación 0
  • Es como una pagina redirigiendose a si misma
  • Skype: [email protected]
  • Twitter: @YaviOS64
    • Ver Perfil
    • Email

Re:[Java] Obtener factores primos de un Número

  • en: Junio 08, 2015, 07:11:08 pm
Vaya!  ;D me paso por la sección de Java y me encuentro con esto, Gracias!  8) ;D
"Eso es lo bueno de internet. De que sirve internet si chateas con tus vecinos??? para eso te sacas unas sillas al fresco y hablais y jugais a las cartas". @windux

Desconectado Adalher

  • *
  • Underc0der
  • Mensajes: 111
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil

Re:[Java] Obtener factores primos de un Número

  • en: Agosto 19, 2019, 08:00:45 pm
Hola hackmin,

pues ¿ya has pensado aquí un poco más en cómo optimizar eso?

-> Incremento: ¿Realmente tienes que incrementar i en 1 o se puede optimizar aquí?
-> ¿Hasta donde tienes que probar? ¿Realmente tienes que probar hasta incluído el número?

Si opinas tener un algoritmo: Pues ¿suministra el números correctos? (¡Aquí se prueba con números pequeños que también se pueden verificar a mano y así! ¡Por tanto prueba una vez tu algoritmo p. e. con el número 8!)

Y sobre todo, 1 no es un factor primo.


Saludos

Desconectado Adalher

  • *
  • Underc0der
  • Mensajes: 111
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil

Re:[Java] Obtener factores primos de un Número

  • en: Agosto 22, 2019, 01:43:53 pm
Hola hackmin,

y no tienes que reinventar la rueda. Alimentar un motor de busqueda con “Java prime factor given number” hubiera sacado a la luz algunas ideas (mas eficientes).

Lamentablemente calculas todos los divisores aunque se trata de factores primos. Por lo tanto, de nuevo mi indicio:
Citar
Si opinas tener un algoritmo: Pues ¿suministra el números correctos? (¡Aquí se prueba con números pequeños que también se pueden verificar a mano y así! ¡Por tanto prueba una vez tu algoritmo p. e. con el número 8!)
Edición: Aunque aquí 8 ya bastaría, 8! Ya es algo grande.

Osea, por un lado se tiene que verificar 2, naturalmente. Entonces se puede seguir con 3 en dos pasos.

Si se tiene un divisor, entonces se verifica si el divisor se repite múltiples de veces. Por lo tanto se debe dividir el número por el divisor y luego seguir con el resultado. De allí que sugerí el 8 como ejemplo.

8%2 = 0 -> 2 es un divisor, 8/2 = 4.
Verificamos 4 de nuevo - 4%2 = 0 -> Es un divisor, 4/2 = 2
Verificamos 2 de nuevo - 2%2 = 0 -> Es nuevamente un divisor, 2/2 = 1 -> Final.
Factorización en números primos de 8 es, por consiguiente, 2,2,2.

Por tanto, que se puede identificar en este ejemplo?:
a) Si se ha encontrado un divisor, el final siempre se desplaza.
b) Se debe verificar un divisor múltiples de veces.
c) El final se tiene que definir. Aquí se puede proceder fácilmente: Contador -> Raíz del número restante -> En ese caso es el número restante el último divisor. Osea en el ejemplo tuvimos número restante 4, contador 2 -> Éxito, nuevo número restante 2, prueba: 2> Raiz de 2: ==> Número restante es el último divisor.

Quizás se puede todavía pensar que se prueba: Número restante == Contador ->. En ese caso se ahorra una vez la raíz. Pero esa optimización no la veo como algo tan alucinante porque complica un poco el algoritmo y, en mi opinión, no satisface el principio KISS.

Con esto, ojala que esto esté claro:
Fraccionamiento en factores primos.
El posible algoritmo.

Y si ya lo he puesto tan lejos como pretexto, entonces también puedo dar un ejemplo de implementación:
Código: Java
  1.        
  2. import java.util.ArrayList;
  3. import java.util.List;
  4.  
  5. public class PrimeFactor {
  6.  
  7.     public static List<Long> getPrimeFactors(final long number) {
  8.         List<Long> result = new ArrayList<>();
  9.         long counter = 2;
  10.         long reminder = number;
  11.         while (counter < You are not allowed to view links. Register or Login.sqrt(reminder)) {
  12.             while (reminder % counter == 0) {
  13.                 result.add(counter);
  14.                 reminder=reminder/counter;
  15.             }
  16.  
  17.             counter = (counter==2) ? 3 : counter+1;
  18.         }
  19.  
  20.         if (reminder > 1) {
  21.             result.add(reminder);
  22.         }
  23.  
  24.         return result;
  25.     }
  26.  
  27.     public static void main(You are not allowed to view links. Register or Login[] args) {
  28.         You are not allowed to view links. Register or Login.out.println("8 fraccionado: " + getPrimeFactors(<img src="https://underc0de.org/foro/Smileys/default/cool.gif" alt="8&#41;" title="Cool" class="smiley" />);
  29.         You are not allowed to view links. Register or Login.out.println("600851475143 fraccionado: " + getPrimeFactors(600851475143L));
  30.     }
  31. }
  32.  
Y esto, naturalmente, calcula muy rápido los resultados:
8 fraccionado: [2, 2, 2]
600851475143 fraccionado: [71, 839, 1471, 6857]


Saludos

Desconectado Adalher

  • *
  • Underc0der
  • Mensajes: 111
  • Actividad:
    0%
  • Reputación 0
    • Ver Perfil

Re:[Java] Obtener factores primos de un Número

  • en: Agosto 22, 2019, 01:45:45 pm
Hola hackmin,

si, naturalmente! counter+2 al final. Mientras teclee no puse suficiente atención. (Eso es todo el sentido detrás del código - que a partir del 3 se siga en dos pasos! De lo contrario, lo hubiera hecho un simple counter++;).

Tenía ganas de construir una solución más con la criba de Eratóstenes y, naturalmente, con streams:
Código: Java
  1.        
  2. import static java.util.stream.LongStream.iterate;
  3. import java.util.BitSet;
  4. import java.util.stream.LongStream;
  5. public class PrimeFactors {
  6.   public static void main(You are not allowed to view links. Register or Login[] args) {
  7.     primeFactors(2 * 2 * 2 * 2 * 2 * 109).forEach(You are not allowed to view links. Register or Login.out::println);
  8.   }
  9.   public static LongStream primeFactors(int n) {
  10.     You are not allowed to view links. Register or Login notPrime = new You are not allowed to view links. Register or Login(n);
  11.     return iterate(2, i -> i <= n, i -> notPrime.nextClearBit((int) (i + 1)))
  12.           .peek(i -> iterate(i * i, j -> j <= n, j -> j + i)
  13.                     .forEach(j -> notPrime.set((int) j, true)))
  14.           .flatMap(i -> iterate(n, j -> (j % i) == 0, j -> j / i)
  15.                        .map(__ -> i));
  16.   }
  17. }
  18.  

Una vez había algo así en SO (You are not allowed to view links. Register or Login).


Saludos

 

[Video Curso] Iniciacion a Java por DesarrolloWeb y EscuelaIT Mayo 2014

Iniciado por graphixx

Respuestas: 3
Vistas: 3900
Último mensaje Febrero 23, 2015, 10:13:28 am
por Hu3c0
Como compilar programas Java en la consola de comandos de Windows

Iniciado por tar3kw0rm3d

Respuestas: 2
Vistas: 4234
Último mensaje Junio 04, 2013, 02:55:07 pm
por tar3kw0rm3d
Cheat-Sheet: JAVA - Hoja Guía para que no se me olvide

Iniciado por Denisse

Respuestas: 1
Vistas: 592
Último mensaje Julio 21, 2020, 12:43:49 pm
por DevCode
Java Extremo [Video Cursos Completos] [Español] [ISO] 2009

Iniciado por graphixx

Respuestas: 9
Vistas: 9799
Último mensaje Diciembre 04, 2017, 02:36:34 am
por graphixx
Aprende programación en Java con este sencillo truco

Iniciado por tr0n

Respuestas: 2
Vistas: 2242
Último mensaje Marzo 03, 2020, 04:36:42 pm
por hebrondev