Secuencia de Euclides-Mullin

Dado un número entero N , la tarea es imprimir los primeros N elementos de la Secuencia Euclid-Mullin . La secuencia de Euclid-Mullin es una secuencia de números primos donde cada elemento es el menor factor primo de uno más el producto de todos los elementos anteriores. La secuencia lleva el nombre del antiguo matemático griego Euclides . Ejemplos:

Entrada: N = 14 Salida: 2 3 7 43 13 53 5 6221671 38709183810571 139 2801 11 17 5471

Enfoque: La sucesión de Euclid-Mullin es una sucesión de números primos donde el n-ésimo número de sucesión es:  Por lo tanto, ejecutaremos un ciclo de 1 a N y tomaremos un producto variable que inicialmente es 1 y contendrá el producto de todos los números anteriores. elementos. Luego encontraremos el factor primo más pequeño de (1 + producto) en tiempo O(sqrt(n)) e imprimiremos el número. Tenga en cuenta que el código no puede imprimir números después del elemento 14 porque el producto se vuelve demasiado grande y encontrar su factor primo más pequeño lleva mucho tiempo. A continuación se muestra la implementación del enfoque anterior: 

// Java implementation of the approach
import java.math.BigInteger;
class GFG {
 
    // Function to return the smallest prime factor of n
    static BigInteger smallestPrimeFactor(BigInteger n)
    {
 
        // Initialize i = 2
        BigInteger i = BigInteger.valueOf(2);
 
        // While i <= sqrt(n)
        while ((i.multiply(i)).compareTo(n) <= 0) {
 
            // If n is divisible by i
            if (n.mod(i).compareTo(BigInteger.ZERO) == 0)
                return i;
 
            // Increment i
            i = i.add(BigInteger.ONE);
        }
        return n;
    }
 
    // Function to print the first n
    // terms of the required sequence
    static void solve(BigInteger n)
    {
        // To store the product of the previous terms
        BigInteger product = BigInteger.ONE;
 
        // Traverse the prime numbers
        BigInteger i = BigInteger.ZERO;
        while (i.compareTo(n) < 0) {
 
            // Current term will be smallest prime
            // factor of (1 + product of all previous terms)
            BigInteger num = smallestPrimeFactor(product.add(BigInteger.ONE));
 
            // Print the current term
            System.out.print(num + " ");
 
            // Update the product
            product = product.multiply(num);
            i = i.add(BigInteger.ONE);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Find the first 14 terms of the sequence
        BigInteger b = BigInteger.valueOf(14);
        solve(b);
    }
}

# Python3 implementation of the approach
 
# Function to return the smallest prime factor of n
def smallestPrimeFactor(n):
 
    # Initialize i = 2
    i = 2
 
    # While i <= sqrt(n)
    while (i * i) <= n :
 
        # If n is divisible by i
        if n % i == 0:
            return i
 
        # Increment i
        i += 1
    return n
 
# Function to print the first n
# terms of the required sequence
def solve(n):
 
    # To store the product of the previous terms
    product = 1
 
    # Traverse the prime numbers
    i = 0
    while i < n:
 
        # Current term will be smallest prime
        # factor of (1 + product of all previous terms)
        num = smallestPrimeFactor(product + 1)
 
        # Print the current term
        print(num, end=' ')
 
        # Update the product
        product = product * num
        i += 1
 
# Driver code
# Find the first 14 terms of the sequence
b = 14
solve(b)
 
# This code is contributed by divyamohan123

2 3 7 43 13 53 5 6221671 38709183810571 139 2801 11 17 5471

Complejidad de tiempo: O(n*sqrt(n))

Espacio Auxiliar: O(1)