Número semiprimo más pequeño con al menos N diferencia entre cualquiera de sus dos divisores

Dado un entero positivo N , la tarea es encontrar el número semiprimo más pequeño tal que la diferencia entre cualquiera de sus dos divisores sea al menos N .

Ejemplos:

Entrada: N = 2
Salida: 15
Explicación:
Los divisores de 15 son 1, 3, 5 y 15 y la diferencia entre cualquiera de sus dos divisores es mayor o igual a N(= 2).

Entrada: N = 3
Salida: 55

Enfoque: El problema dado se puede resolver encontrando dos números primos (por ejemplo, X e Y ) cuya diferencia sea al menos N. La idea es encontrar el primer número primo, es decir, X mayor que N , y el segundo número primo, es decir, Y mayor que (N + X) . Siga los pasos a continuación para resolver el problema:

Inicialice una array booleana prime[] para almacenar los números primos hasta 10 ⁵ utilizando la criba de Eratóstenes de modo que si i es primo , entonces prime[i] será verdadero . De lo contrario, falso .
Inicialice dos variables, digamos X e Y , que almacenan ambos números primos de modo que el producto de X e Y sea el número semiprimo resultante.
Itere un ciclo desde (N + 1) usando la variable i y si el valor de prime[i] es verdadero , entonces actualice el valor de X como i y salga del ciclo .
Iterar un ciclo desde (N + X) usando la variable i y si el valor de prime[i] es verdadero , entonces actualice el valor de Y como i y salga del ciclo .
Después de completar los pasos anteriores, imprima el producto de X e Y como el número semiprimo resultante.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define MAX 100001
using namespace std;
 
// Function to find all the prime
// numbers using Sieve of Eratosthenes
void SieveOfEratosthenes(bool prime[])
{
    // Set 0 and 1 as non-prime
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p < MAX; p++) {
 
        // If p is a prime
        if (prime[p] == true) {
 
            // Set all multiples
            // of p as non-prime
            for (int i = p * p; i < MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the smallest semi-prime
// number having a difference between any
// of its two divisors at least N
void smallestSemiPrime(int n)
{
    // Stores the prime numbers
    bool prime[MAX];
    memset(prime, true, sizeof(prime));
 
    // Fill the prime array
    SieveOfEratosthenes(prime);
 
    // Initialize the first divisor
    int num1 = n + 1;
 
    // Find the value of the first
    // prime number
    while (prime[num1] != true) {
        num1++;
    }
 
    // Initialize the second divisor
    int num2 = num1 + n;
 
    // Find the second prime number
    while (prime[num2] != true) {
        num2++;
    }
 
    // Print the semi-prime number
    cout << num1 * 1LL * num2;
}
 
// Driver Code
int main()
{
    int N = 2;
    smallestSemiPrime(N);
 
    return 0;
}

Java

// Java approach for the above approach
class GFG{
 
static int MAX = 100001;
 
// Function to find all the prime
// numbers using Sieve of Eratosthenes
static void SieveOfEratosthenes(boolean prime[])
{
     
    // Set 0 and 1 as non-prime
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p < MAX; p++)
    {
         
        // If p is a prime
        if (prime[p] == true)
        {
             
            // Set all multiples
            // of p as non-prime
            for(int i = p * p; i < MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the smallest semi-prime
// number having a difference between any
// of its two divisors at least N
static void smallestSemiPrime(int n)
{
     
    // Stores the prime numbers
    boolean[] prime = new boolean[MAX];
 
    for(int i = 0; i < prime.length; i++)
    {
        prime[i] = true;
    }
 
    // Fill the prime array
    SieveOfEratosthenes(prime);
 
    // Initialize the first divisor
    int num1 = n + 1;
 
    // Find the value of the first
    // prime number
    while (prime[num1] != true)
    {
        num1++;
    }
 
    // Initialize the second divisor
    int num2 = num1 + n;
 
    // Find the second prime number
    while (prime[num2] != true)
    {
        num2++;
    }
 
    // Print the semi-prime number
    System.out.print(num1 * num2);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2;
     
    smallestSemiPrime(N);
}
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
MAX = 100001
 
# Function to find all the prime
# numbers using Sieve of Eratosthenes
def SieveOfEratosthenes(prime):
 
    # Set 0 and 1 as non-prime
    prime[0] = False
    prime[1] = False
 
    p = 2
     
    while p * p < MAX:
 
        # If p is a prime
        if (prime[p] == True):
 
            # Set all multiples
            # of p as non-prime
            for i in range(p * p, MAX, p):
                prime[i] = False
 
        p += 1
 
# Function to find the smallest semi-prime
# number having a difference between any
# of its two divisors at least N
def smallestSemiPrime(n):
 
    # Stores the prime numbers
    prime = [True] * MAX
 
    # Fill the prime array
    SieveOfEratosthenes(prime)
 
    # Initialize the first divisor
    num1 = n + 1
 
    # Find the value of the first
    # prime number
    while (prime[num1] != True):
        num1 += 1
 
    # Initialize the second divisor
    num2 = num1 + n
 
    # Find the second prime number
    while (prime[num2] != True):
        num2 += 1
 
    # Print the semi-prime number
    print(num1 * num2)
 
# Driver Code
if __name__ == "__main__":
 
    N = 2
     
    smallestSemiPrime(N)
 
# This code is contributed by ukasp

C#

// C# program for the above approach
using System;
 
class GFG{
     
static int MAX = 100001;
 
// Function to find all the prime
// numbers using Sieve of Eratosthenes
static void SieveOfEratosthenes(bool[] prime)
{
     
    // Set 0 and 1 as non-prime
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p < MAX; p++)
    {
         
        // If p is a prime
        if (prime[p] == true)
        {
             
            // Set all multiples
            // of p as non-prime
            for(int i = p * p; i < MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to find the smallest semi-prime
// number having a difference between any
// of its two divisors at least N
static void smallestSemiPrime(int n)
{
     
    // Stores the prime numbers
    bool[] prime = new bool[MAX];
     
    for(int i = 0; i < prime.Length; i++)
    {
        prime[i] = true;
    }
     
    // Fill the prime array
    SieveOfEratosthenes(prime);
 
    // Initialize the first divisor
    int num1 = n + 1;
 
    // Find the value of the first
    // prime number
    while (prime[num1] != true)
    {
        num1++;
    }
 
    // Initialize the second divisor
    int num2 = num1 + n;
 
    // Find the second prime number
    while (prime[num2] != true)
    {
        num2++;
    }
 
    // Print the semi-prime number
    Console.Write(num1 * num2);
}
 
// Driver code
static void Main()
{
    int N = 2;
     
    smallestSemiPrime(N);
}
}
 
// This code is contributed by abhinavjain194

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
let MAX = 100001;
  
// Function to find all the prime
// numbers using Sieve of Eratosthenes
function SieveOfEratosthenes(prime)
{
      
    // Set 0 and 1 as non-prime
    prime[0] = false;
    prime[1] = false;
  
    for(let p = 2; p * p < MAX; p++)
    {
          
        // If p is a prime
        if (prime[p] == true)
        {
              
            // Set all multiples
            // of p as non-prime
            for(let i = p * p; i < MAX; i += p)
                prime[i] = false;
        }
    }
}
  
// Function to find the smallest semi-prime
// number having a difference between any
// of its two divisors at least N
function smallestSemiPrime(n)
{
      
    // Stores the prime numbers
    let prime = Array.from({length: MAX}, (_, i) => 0);
  
    for(let i = 0; i < prime.length; i++)
    {
        prime[i] = true;
    }
  
    // Fill the prime array
    SieveOfEratosthenes(prime);
  
    // Initialize the first divisor
    let num1 = n + 1;
  
    // Find the value of the first
    // prime number
    while (prime[num1] != true)
    {
        num1++;
    }
  
    // Initialize the second divisor
    let num2 = num1 + n;
  
    // Find the second prime number
    while (prime[num2] != true)
    {
        num2++;
    }
  
    // Print the semi-prime number
   document.write(num1 * num2);
}
 
// Driver code
 
    let N = 2;
      
    smallestSemiPrime(N);
   
  // This code is contributed by code_hunt.
</script>

Producción:

Complejidad de tiempo: O(M * log(log(M))), donde M es el tamaño de la array prime[]
Espacio auxiliar: O(M)

Publicación traducida automáticamente

Artículo escrito por rohitmanathiya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta