K pares primos distantes en un rango dado

Dados dos enteros L, R y un entero K , la tarea es imprimir todos los pares de números primos del rango dado cuya diferencia es K.

Ejemplos:

Entrada: L = 1, R = 19, K = 6
Salida: (5, 11) (7, 13) (11, 17) (13, 19)
Explicación: Los pares de números primos con diferencia 6 son (5, 11 ), (7, 13), (11, 17) y (13, 19).

Entrada: L = 4, R = 13, K = 2
Salida: (5, 7) (11, 13)
Explicación: Los pares de números primos con diferencia 2 son (5, 7) y (11, 13).

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles que tengan una diferencia K del rango dado y verificar si ambos elementos del par son números primos o no. Si existe tal par, imprima ese par. 

Complejidad de tiempo: O(sqrt((N))*(R – L + 1) 2 ), donde N es cualquier número en el rango [L, R] .
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar la criba de Eratóstenes para encontrar todos los números primos en el rango dado [L, R] y almacenarlos en un mapa_desordenado M . Ahora, recorra cada valor (digamos val ) en M y si (val + K) también está presente en el mapa M , imprima el par.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate prime numbers
// in the given range [L, R]
void findPrimeNos(int L, int R,
                  unordered_map<int,
                                int>& M)
{
    // Store all value in the range
    for (int i = L; i <= R; i++) {
        M[i]++;
    }
 
    // Erase 1 as its non-prime
    if (M.find(1) != M.end()) {
        M.erase(1);
    }
 
    // Perform Sieve of Eratosthenes
    for (int i = 2; i <= sqrt(R); i++) {
 
        int multiple = 2;
 
        while ((i * multiple) <= R) {
 
            // Find current multiple
            if (M.find(i * multiple)
                != M.end()) {
 
                // Erase as it is a
                // non-prime
                M.erase(i * multiple);
            }
 
            // Increment multiple
            multiple++;
        }
    }
}
 
// Function to print all the prime pairs
// in the given range that differs by K
void getPrimePairs(int L, int R, int K)
{
    unordered_map<int, int> M;
 
    // Generate all prime number
    findPrimeNos(L, R, M);
 
    // Traverse the Map M
    for (auto& it : M) {
 
        // If it.first & (it.first + K)
        // is prime then print this pair
        if (M.find(it.first + K)
            != M.end()) {
            cout << "(" << it.first
                 << ", "
                 << it.first + K
                 << ") ";
        }
    }
}
 
// Driver Code
int main()
{
    // Given range
    int L = 1, R = 19;
 
    // Given K
    int K = 6;
 
    // Function Call
    getPrimePairs(L, R, K);
 
    return 0;
}

Java

// Java program for the
// above approach
import java.util.*;
 
class solution{
 
// Function to generate prime
// numbers in the given range [L, R]
static void findPrimeNos(int L, int R,
                         Map<Integer,
                             Integer> M,
                         int K)
{
  // Store all value in the range
  for (int i = L; i <= R; i++)
  {
    if(M.get(i) != null)
      M.put(i, M.get(i) + 1);
    else
      M.put(i, 1);
  }
 
  // Erase 1 as its
  // non-prime
  if (M.get(1) != null)
  {
    M.remove(1);
  }
 
  // Perform Sieve of
  // Eratosthenes
  for (int i = 2;
           i <= Math.sqrt(R); i++)
  {
    int multiple = 2;
     
    while ((i * multiple) <= R)
    {
      // Find current multiple
      if (M.get(i * multiple) != null)
      {
        // Erase as it is a
        // non-prime
        M.remove(i * multiple);
      }
 
      // Increment multiple
      multiple++;
    }
  }
 
  // Traverse the Map M
  for (Map.Entry<Integer,
                 Integer> entry :
       M.entrySet()) 
  {
    // If it.first & (it.first + K)
    // is prime then print this pair
 
    if (M.get(entry.getKey() + K) != null)
    {
      System.out.print("(" + entry.getKey() +
                       ", " + (entry.getKey() +
                       K) + ") ");
    }
  }
}
 
// Function to print all
// the prime pairs in the
// given range that differs by K
static void getPrimePairs(int L,
                          int R, int K)
{
  Map<Integer,
      Integer> M = new HashMap<Integer,
                               Integer>(); 
 
  // Generate all prime number
  findPrimeNos(L, R, M, K);
}
 
// Driver Code
public static void main(String args[])
{
  // Given range
  int L = 1, R = 19;
 
  // Given K
  int K = 6;
 
  // Function Call
  getPrimePairs(L, R, K);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Python3

# Python3 program for the above approach
from math import sqrt
 
# Function to generate prime numbers
# in the given range [L, R]
def findPrimeNos(L, R, M):
     
    # Store all value in the range
    for i in range(L, R + 1):
        M[i] = M.get(i, 0) + 1
 
    # Erase 1 as its non-prime
    if (1 in M):
        M.pop(1)
 
    # Perform Sieve of Eratosthenes
    for i in range(2, int(sqrt(R)) + 1, 1):
        multiple = 2
 
        while ((i * multiple) <= R):
             
            # Find current multiple
            if ((i * multiple) in M):
                 
                # Erase as it is a
                # non-prime
                M.pop(i * multiple)
 
            # Increment multiple
            multiple += 1
 
# Function to print all the prime pairs
# in the given range that differs by K
def getPrimePairs(L, R, K):
     
    M = {}
 
    # Generate all prime number
    findPrimeNos(L, R, M)
 
    # Traverse the Map M
    for key, values in M.items():
         
        # If it.first & (it.first + K)
        # is prime then print this pair
        if ((key + K) in M):
            print("(", key, ",",
                  key + K, ")", end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given range
    L = 1
    R = 19
 
    # Given K
    K = 6
 
    # Function Call
    getPrimePairs(L, R, K)
 
# This code is contributed by bgangwar59

C#

// C# program for the
// above approach
using System;
using System.Collections.Generic;
class solution{
 
// Function to generate prime
// numbers in the given range [L, R]
static void findPrimeNos(int L, int R,
                         Dictionary<int,
                         int> M, int K)
{
  // Store all value in the range
  for (int i = L; i <= R; i++)
  {
      if(M.ContainsKey(i))
      M.Add(i, M[i] + 1);
    else
      M.Add(i, 1);
  }
 
  // Erase 1 as its
  // non-prime
  if (M[1] != 0)
  {
    M.Remove(1);
  }
 
  // Perform Sieve of
  // Eratosthenes
  for (int i = 2;
           i <= Math.Sqrt(R); i++)
  {
    int multiple = 2;
     
    while ((i * multiple) <= R)
    {
      // Find current multiple
      if (M.ContainsKey(i * multiple))
      {
        // Erase as it is a
        // non-prime
        M.Remove(i * multiple);
      }
 
      // Increment multiple
      multiple++;
    }
  }
 
  // Traverse the Map M
  foreach (KeyValuePair<int, 
                        int> entry in  M) 
  {
    // If it.first & (it.first + K)
    // is prime then print this pair
 
    if (M.ContainsKey(entry.Key + K))
    {
      Console.Write("(" + entry.Key +
                    ", " + (entry.Key +
                    K) + ") ");
    }
  }
}
 
// Function to print all
// the prime pairs in the
// given range that differs by K
static void getPrimePairs(int L,
                          int R, int K)
{
  Dictionary<int,
             int> M = new Dictionary<int,
                                     int>(); 
   
  // Generate all prime number
  findPrimeNos(L, R, M, K);
}
 
// Driver Code
public static void Main(String []args)
{
  // Given range
  int L = 1, R = 19;
 
  // Given K
  int K = 6;
 
  // Function Call
  getPrimePairs(L, R, K);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to generate prime numbers
// in the given range [L, R]
function findPrimeNos(L, R, M)
{
     
    // Store all value in the range
    for(var i = L; i <= R; i++)
    {
        if (M.has(i))
            M.set(i, M.get(i) + 1)
        else
            M.set(i, 1)
    }
 
    // Erase 1 as its non-prime
    if (M.has(1))
    {
        M.delete(1);
    }
 
    // Perform Sieve of Eratosthenes
    for(var i = 2; i <= parseInt(Math.sqrt(R)); i++)
    {
        var multiple = 2;
 
        while ((i * multiple) <= R)
        {
             
            // Find current multiple
            if (M.has(i * multiple))
            {
                 
                // Erase as it is a
                // non-prime
                M.delete(i * multiple);
            }
 
            // Increment multiple
            multiple++;
        }
    }
    return M;
}
 
// Function to print all the prime pairs
// in the given range that differs by K
function getPrimePairs(L, R,  K)
{
    var M = new Map();
 
    // Generate all prime number
    M = findPrimeNos(L, R, M);
 
    // Traverse the Map M
    M.forEach((value, key) => {
         
        // If it.first & (it.first + K)
        // is prime then print this pair
        if (M.has(key + K))
        {
            document.write("(" + key + ", " +
                          (key + K) + ") ");
        }
    });
}
 
// Driver Code
 
// Given range
var L = 1, R = 19;
 
// Given K
var K = 6;
 
// Function Call
getPrimePairs(L, R, K);
 
// This code is contributed by rutvik_56
 
</script>
Producción

(5, 11) (7, 13) (11, 17) (13, 19) 

Complejidad de tiempo: O(N*log*(log(N)) + sqrt(R – L)), donde N = R – L + 1
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *