Encuentra factores de un número dado en Java

En este artículo, aprenderemos cómo encontrar distintos factores o divisores de un número dado en Java.

Encuentra factores de un número dado en Java

Método uno: enfoque de fuerza bruta

Un enfoque sencillo sería atravesar todos los números desde 1 hasta n y ver si dividen n correctamente (es decir, dar el resto cero). Si es así, es un factor más, no un factor.

Código de ejemplo:

import java.io.*;

class test {
  public static void main(String[] args) {
    int n = 24;

    for (int i = 1; i <= n; i++) {
      if (n % i == 0)
        System.out.println(i);
    }
  }
}

Producción :

1
2
3
4
6
8
12
24

Método dos: atravesar hasta n/2

Del primer método, podemos observar que en lugar de recorrer hasta n, podemos detenerlo en n/2 porque cualquier número mayor que n/2 nunca puede ser el factor del número n excepto el número en sí.

Por ejemplo, el número n es 100, por lo que n/2 es 50, por lo que cualquier número mayor que 50, como 51 o 52, nunca puede ser el factor de 100.

Código de ejemplo:

import java.io.*;

class GFG {
  public static void main(String[] args) {
    int n = 24;

    for (int i = 1; i <= n / 2; i++) {
      if (n % i == 0)
        System.out.println(i);
    }

    System.out.println(n);
  }
}

En el código anterior, hemos escrito una instrucción de impresión adicional después del bucle, ya que el número n en sí mismo es un factor.

Producción :

1
2
3
4
6
8
12
24

Método tres: atravesar hasta sqrt(n)

Podemos optimizar aún más el segundo método haciendo una pequeña observación. Si miramos de cerca, vemos que los factores ocurren en pares.

Por ejemplo, n = 100 y sus factores son 1,2,4,5, 10, 20, 25, 50, 100. Entonces, los diferentes pares posibles aquí son (1,100), (2,50), (4,25), (5,20), (10,10).

Por lo tanto, al máximo, tenemos que comprobar los números hasta sqrt(n); en este caso es 10. El último (10,10) es un caso especial ya que sabemos que el número es un factor.

Código de ejemplo:

import java.io.*;
class GFG {
  public static void main(String[] args) {
    int num = 24;

    for (int i = 1; i <= Math.sqrt(num); i++) {
      if (num % i == 0) {
        if (num / i == i)
          System.out.println(i);

        else {
          System.out.println(i);
          System.out.println(num / i);
        }
      }
    }
  }
}

Producción :

1
24
2
12
3
8
4
6

En el resultado anterior, los factores no están ordenados. Podemos obtener la salida ordenada usando el espacio auxiliar.

Código de ejemplo:

import java.io.*;
import java.util.*;

class GFG {
  public static void main(String[] args) {
    int num = 24;
    ArrayList<Integer> store = new ArrayList<>();
    for (int i = 1; i <= Math.sqrt(num); i++) {
      if (num % i == 0) {
        if (num / i == i)
          System.out.println(i);

        else {
          System.out.println(i);
          store.add(num / i);
        }
      }
    }

    for (int j = store.size() - 1; j >= 0; j--) System.out.println(store.get(j));
  }
}

Producción :

1
2
3
4
6
8
12
24

En el código anterior, usamos una ArrayList para almacenar algunos factores y luego imprimimos el contenido de la ArrayList en el orden inverso al final.