Algoritmo de división de prueba para factorización prima

En este artículo, se analiza el método de división de prueba para comprobar si un número es primo o no. Dado un número N, la tarea es comprobar si el número es primo o no. 

Ejemplos: 

Entrada: N = 433 
Salida: Prime 
Explicación: 
Los únicos factores de 433 son 1 y 433. Por lo tanto, es un número primo. 

Entrada: N = 1263 
Salida: Compuesto 
Explicación: 
Los factores de 1263 son 1, 3, 421, 1263. Por lo tanto, es un número compuesto. 

Enfoque ingenuo: por definición, un número primo es un número entero mayor que 1, que solo es divisible por 1 y por sí mismo. Por lo tanto, inicializamos un bucle de 2 a N – 1 y verificamos la divisibilidad. El siguiente es el pseudocódigo para el enfoque:  

N <- input
initialise: i <- 2
while(i ≤ N - 1):
    if(N % i == 0):
        return "Composite"
return "Prime" 

Análisis de la Complejidad del Tiempo: 

• Para cualquier número N dado , el bucle while se ejecuta N – 2 veces. Por lo tanto, la complejidad de tiempo para el ciclo while es O(N) .
• La comprobación de divisibilidad se realiza en tiempo constante. Por lo tanto, la complejidad de tiempo para la condición if en el ciclo while es O(1) .
• Por lo tanto, la complejidad temporal general del enfoque anterior es O(N) .

Método de división de prueba: la verificación de primalidad se puede realizar de manera más eficiente mediante el concepto del método de división de prueba. El método de división de prueba es una de las técnicas de factorización cruciales pero una de las más fáciles cuando se trata de factorización de enteros. 

Observación: El método anterior funciona con la observación de que el factor máximo para cualquier número N siempre es menor o igual que la raíz cuadrada (N). Esta conclusión se puede derivar de la siguiente manera: 

• De la escuela de aritmética, es un hecho conocido que cualquier número compuesto se construye a partir de dos o más números primos.
• Sean los factores de N n1, n2, etc. Los factores son mayores solo cuando existen dos factores n1 y n2 para el número N.
• Por lo tanto, supongamos que n1 y n2 son los dos factores más grandes para el número N. Estos números n1 y n2 pueden ser mayores solo cuando tanto n1 como n2 son iguales .
• Sea n1 = n2 = n . Por lo tanto, N = n * n . Por lo tanto, el factor más grande posible para N es la raíz cuadrada (N) .

Enfoque: A partir de la observación anterior, el enfoque de este algoritmo es sencillo. La idea es que en lugar de verificar hasta N – 1 para un factor, solo verificamos hasta la raíz cuadrada (N) . 

A continuación se muestra la implementación del enfoque anterior:  

// CPP implementation of
// Trial Division Algorithm
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to check if a number is
// a prime number or not
int TrialDivision(int N){
 
    // Initializing with the value 2
    // from where the number is checked
    int i = 2;
 
    // Computing the square root of
    // the number N
    int k = ceil(sqrt(N));
 
    // While loop till the
    // square root of N
    while(i<= k){
 
        // If any of the numbers between
        // [2, sqrt(N)] is a factor of N
        // Then the number is composite
        if(N % i == 0)
            return 0;
        i += 1;
    }
 
    // If none of the numbers is a factor,
    // then it is a prime number
    return 1;
}
 
// Driver code
int main()
{
    int N = 49;
    int p = TrialDivision(N);
 
    // To check if a number is a prime or not
    if(p)
        cout << ("Prime");
    else
        cout << ("Composite");
 
    return 0;
}
 
// This code is contributed by mohit kumar 29

// Java implementation of
// Trial Division Algorithm
import java.util.*;
  
class GFG{
   
// Function to check if a number is
// a prime number or not
static int TrialDivision(int N){
 
    // Initializing with the value 2
    // from where the number is checked
    int i = 2;
 
    // Computing the square root of
    // the number N
    int k =(int) Math.ceil(Math.sqrt(N));
 
    // While loop till the
    // square root of N
    while(i<= k){
 
        // If any of the numbers between
        // [2, sqrt(N)] is a factor of N
        // Then the number is composite
        if(N % i == 0)
            return 0;
        i += 1;
    }
 
    // If none of the numbers is a factor,
    // then it is a prime number
    return 1;
}
 
// Driver Code
public static void main(String[] args)
{
  
    int N = 49;
    int p = TrialDivision(N);
 
    // To check if a number is a prime or not
    if(p != 0)
        System.out.print("Prime");
    else
        System.out.print("Composite");
 
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 implementation of
# Trial Division Algorithm
 
# Function to check if a number is
# a prime number or not
def TrialDivision(N):
 
    # Initializing with the value 2
    # from where the number is checked
    i = 2
 
    # Computing the square root of
    # the number N
    k = int(N ** 0.5)
 
    # While loop till the
    # square root of N
    while(i<= k):
 
        # If any of the numbers between
        # [2, sqrt(N)] is a factor of N
        # Then the number is composite
        if(N % i == 0):
            return 0
        i += 1
 
    # If none of the numbers is a factor,
    # then it is a prime number
    return 1
     
# Driver code
if __name__ == "__main__":
    N = 49
    p = TrialDivision(N)
 
# To check if a number is a prime or not
    if(p):
        print("Prime")
    else:
        print("Composite")
        

// C# implementation of
// Trial Division Algorithm
using System;
 
class GFG{
 
// Function to check if a number is
// a prime number or not
static int TrialDivision(int N){
 
    // Initializing with the value 2
    // from where the number is checked
    int i = 2;
 
    // Computing the square root of
    // the number N
    int k =(int) Math.Ceiling(Math.Sqrt(N));
 
    // While loop till the
    // square root of N
    while(i<= k){
 
        // If any of the numbers between
        // [2, sqrt(N)] is a factor of N
        // Then the number is composite
        if(N % i == 0)
            return 0;
        i += 1;
    }
 
    // If none of the numbers is a factor,
    // then it is a prime number
    return 1;
}
 
// Driver Code
public static void Main()
{
 
    int N = 49;
    int p = TrialDivision(N);
 
    // To check if a number is a prime or not
    if(p != 0)
        Console.Write("Prime");
    else
        Console.Write("Composite");
 
}
}
 
// This code is contributed by AbhiThakur

<script>
 
// JavaScript implementation of
// Trial Division Algorithm
 
 
// Function to check if a number is
// a prime number or not
function TrialDivision(N){
 
    // Initializing with the value 2
    // from where the number is checked
    let i = 2;
 
    // Computing the square root of
    // the number N
    let k = Math.ceil(Math.sqrt(N));
 
    // While loop till the
    // square root of N
    while(i<= k){
 
        // If any of the numbers between
        // [2, sqrt(N)] is a factor of N
        // Then the number is composite
        if(N % i == 0)
            return 0;
        i += 1;
    }
 
    // If none of the numbers is a factor,
    // then it is a prime number
    return 1;
}
 
// Driver code
 
let N = 49;
let p = TrialDivision(N);
 
// To check if a number is a prime or not
if(p)
    document.write("Prime");
else
    document.write("Composite");
 
// This code is contributed by gfgking
 
</script>

Composite

Análisis de la Complejidad del Tiempo: 

• El ciclo while se ejecuta por un máximo de raíces cuadradas (N) veces. Por lo tanto, la complejidad temporal del ciclo while es O(sqrt(N)) .
• El tiempo de ejecución de todas las condiciones si son constantes. Por lo tanto, la complejidad temporal de las sentencias if es O(1) .
• Por lo tanto, la complejidad temporal general es O(sqrt(N)) .

Método de división de prueba optimizado: el método de división de prueba anterior se puede optimizar aún más eliminando todos los números pares en el rango [2, K] donde K = raíz cuadrada (N) ya que 2 es el único número primo par. La complejidad general sigue siendo la misma, pero el número de ejecuciones se reduce a la mitad.

Nota: La optimización realizada en el método de división de prueba puede parecer muy pequeña, ya que este método es casi similar al enfoque ingenuo, excepto por el número de iteraciones. Sin embargo, esto reduce drásticamente el número de cálculos para valores más altos de N. Esto se explica mediante el siguiente gráfico trazado frente a los tiempos de ejecución correspondientes de los algoritmos: