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