Programa Java para realizar la factorización única de un número dado

Dado un número n , la tarea es escribir un programa eficiente para imprimir todos los factores primos únicos de n. 

Ejemplo

Input: 12
Output: 2, 3
Explanation: All prime factors or 12 are 2, 2, 3. In those factors, unique factors
         are 2 and 3.

Input: 315 
Output: 3, 5, 7

Pasos para encontrar todos los factores primos

1) Mientras que n es divisible por 2, imprima 2 y divida n por 2.

2) Después del paso 1, n debe ser impar. Ahora inicia un bucle desde i = 3 hasta la raíz cuadrada de n. Mientras i divide n, imprima i y divida n entre i, incremente i en 2 y continúe.

3) Si n es un número primo y es mayor que 2, entonces n no se convertirá en 1 por los dos pasos anteriores. Entonces imprima n si es mayor que 2.

En el segundo paso, el bucle se ejecuta en la raíz cuadrada de n porque los pares para el producto del número n solo son posibles cuando un número es menor que mayor que la raíz cuadrada de n y el segundo número es mayor e igual a la raíz cuadrada. de n.

Por ejemplo, sea n =16 la raíz cuadrada de 16 es 4 y los factores de 16 son 1×16, 16×1, 2×8, 8×2, 4×4 en esta secuencia el primer número debe ser menor o igual a la raíz cuadrada de n y el segundo número es mayor que e igual a la raíz cuadrada de n.

Demostración matemática:

1. Sea x < sqrt(n) y y < sqrt(n) multiplique ambas ecuaciones x×y < n, por lo tanto, cuando cualquier x e y sean menores que n. El producto de cualquier x e y siempre es menor que n.
2. Sea x > sqrt(n) y y > sqrt(n) multiplique ambas ecuaciones x×y > n, por lo tanto, cuando cualquier xey sea menor que n. El producto de cualquier xey es siempre menor que n.
3. Deje que un número esté por debajo de sqrt (n) y el segundo número por encima de sqrt (n). En este caso siempre hay al menos un par de números cuyo producto es n. Sean x e y los dos números cuyo producto es n. Podemos escribir x = sqrt(n) * sqrt(n)/y ⇾ ecuación 1

Hay dos condiciones:

• Cuando y < sqrt(n) es decir, 1 < sqrt(n)/y podemos escribir la primera ecuación x = sqrt(n)*(1+b) por lo tanto x > sqrt(n)
• Cuando y < sqrt(n) es decir, 1 > sqrt(n)/y podemos escribir la primera ecuación x = sqrt(n)*(1-b) por lo tanto x < sqrt(n).

Por lo tanto, podemos concluir que para x*y=n al menos un número es menor que igual a sqrt(n) o mayor que e igual a sqrt(n)

Este concepto se usa en muchos algoritmos de teoría de números como un tamiz , encontrar todos los divisores de n , etc.
 

Enfoques para encontrar factores primos únicos de un número dado

1. Enfoque usando HashSet 

• Mientras que n es divisible por 2, almacene 2 en el conjunto y divida n por 2.
• Después del paso anterior, n debe ser impar. Ahora inicia un bucle desde i = 3 hasta la raíz cuadrada de n. Mientras i divide n, almacene i en el conjunto y divida n entre i. Después de que no pueda dividir n, incremente i en 2 y continúe.
• Si n es un número primo y es mayor que 2, entonces n no se convertirá en 1 por los dos pasos anteriores. Entonces almacene en el conjunto n si es mayor que 2.

// Java Program to print all unique prime factors
 
import java.io.*;
import java.lang.Math;
import java.util.*;
class GFG {
 
    // A function to print all prime factors
    // of a given number n
    public static void primeFactors(int n,
                                    HashSet<Integer> h)
    {
        // Print the number of 2s that divide n
        while (n % 2 == 0) {
 
            h.add(2);
            n /= 2;
        }
 
        // n must be odd at this point. So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
 
            // While i divides n, print i and divide n
            while (n % i == 0) {
                h.add(i);
                n /= i;
            }
        }
 
        // This condition is to handle the case when
        // n is a prime number greater than 2
        if (n > 2)
            h.add(n);
    }
    static void printFactors(HashSet<Integer> H)
    {
        // Iterator over the HashSet
        Iterator<Integer> It = H.iterator();
 
        // printing the elements of HashSet
        while (It.hasNext()) {
 
            System.out.print(It.next() + " ");
        }
        System.out.println();
    }
    public static void main(String[] args)
    {
        int n = 15;
        HashSet<Integer> h = new HashSet<>();
 
        primeFactors(n, h);
 
        // print the unique factors
        printFactors(h);
    }
}

3 5

 Complejidad de tiempo: O(sqrt(n))
 

2. Acercamiento usando tamiz:

• Marca todos los múltiplos de números hasta sqrt (n) por el motivo mencionado anteriormente, donde n es la longitud máxima de la array.
• La array se ve como un múltiplo de 2 y así sucesivamente hasta la longitud de la array.

• Marque todos los múltiplos restantes de todos los números hasta sqrt (n). Para encontrar los factores de un n-ésimo número.
  • Divide la n con n/dp[n] hasta dp[n]!=n
  • Almacene todos los valores de dp[n] en HashSet o TreeSet y finalmente almacene n en el conjunto.
  • Imprima el conjunto para factores únicos.

// Java Program to print all unique prime factors
 
import java.util.*;
import java.io.*;
 
public class GFG {
    static int dp[] = new int[100001];
 
    static void fill()
    {
        int n = 100000;
        for (int i = 1; i <= n; ++i) {
            dp[i] = i;
        }
       
        // mark the multiply of 2
        for (int i = 2; i <= n; i += 2) {
            dp[i] = 2;
        }
       
        // mark the multiple of less than sqrt(n)
        for (int i = 3; i <= Math.sqrt(n); ++i) {
            for (int j = i * i; j <= n; j += i) {
                if (dp[j] == j) {
                    dp[j] = i;
                }
            }
        }
    }
    static void Factors(int n, HashSet<Integer> h)
    {
 
        // when n is prime number
        if (dp[n] == n) {
            h.add(n);
            return;
        }
        else {
            while (dp[n] != n) {
 
                // Adding the multiple.
                h.add(dp[n]);
                n = n / dp[n];
            }
            h.add(n);
            return;
        }
    }
    static void print(HashSet<Integer> h)
    {
        Iterator<Integer> it = h.iterator();
 
        // printing the elements
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
 
    public static void main(String[] args)
    {
        int n = 21;
        fill();
        HashSet<Integer> h = new HashSet<>();
 
        // finding the factors
        Factors(n, h);
        print(h);
    }
}

3 7

Complejidad de tiempo: O (logn)