Dados dos números enteros L y R , la tarea es encontrar la diferencia mínima entre dos números primos cualesquiera en el rango [L, R] .
Ejemplos:
Entrada: L = 21, R = 50
Salida: 2
(29, 31) y (41, 43) son los únicos pares válidos
que dan la diferencia mínima.Entrada: L = 1, R = 11
Salida: 1
La diferencia entre (2, 3) es mínima.
Acercarse:
- Encuentra todos los números primos hasta R usando la criba de Eratóstenes .
- Ahora, a partir de L , encuentre la diferencia entre dos números primos dentro del rango y actualice la diferencia mínima hasta el momento.
- Si el número de números primos en el rango fuera < 2 , imprima -1 .
- De lo contrario, imprima la diferencia mínima.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5;
bool isPrime[sz + 1];
// Function for Sieve of Eratosthenes
void sieve()
{
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= sz; i++) {
if (isPrime[i]) {
for (int j = i * i; j < sz; j += i) {
isPrime[j] = false;
}
}
}
}
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
int minDifference(int L, int R)
{
// Find the first prime from the range
int fst = 0;
for (int i = L; i <= R; i++) {
if (isPrime[i]) {
fst = i;
break;
}
}
// Find the second prime from the range
int snd = 0;
for (int i = fst + 1; i <= R; i++) {
if (isPrime[i]) {
snd = i;
break;
}
}
// If the number of primes in
// the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference between
// two consecutive primes from the range
int diff = snd - fst;
// Range left to check for primes
int left = snd + 1;
int right = R;
// For every integer in the range
for (int i = left; i <= right; i++) {
// If the current integer is prime
if (isPrime[i]) {
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff) {
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Driver code
int main()
{
// Generate primes
sieve();
int L = 21, R = 50;
cout << minDifference(L, R);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int sz = (int) 1e5;
static boolean []isPrime = new boolean [sz + 1];
// Function for Sieve of Eratosthenes
static void sieve()
{
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= sz; i++)
{
if (isPrime[i])
{
for (int j = i * i; j < sz; j += i)
{
isPrime[j] = false;
}
}
}
}
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
static int minDifference(int L, int R)
{
// Find the first prime from the range
int fst = 0;
for (int i = L; i <= R; i++)
{
if (isPrime[i])
{
fst = i;
break;
}
}
// Find the second prime from the range
int snd = 0;
for (int i = fst + 1; i <= R; i++)
{
if (isPrime[i])
{
snd = i;
break;
}
}
// If the number of primes in
// the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference between
// two consecutive primes from the range
int diff = snd - fst;
// Range left to check for primes
int left = snd + 1;
int right = R;
// For every integer in the range
for (int i = left; i <= right; i++)
{
// If the current integer is prime
if (isPrime[i])
{
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff)
{
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Driver code
public static void main(String []args)
{
// Generate primes
sieve();
int L = 21, R = 50;
System.out.println(minDifference(L, R));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach from math import sqrt sz = int(1e5); isPrime = [True] * (sz + 1); # Function for Sieve of Eratosthenes def sieve() : isPrime[0] = isPrime[1] = False; for i in range(2, int(sqrt(sz)) + 1) : if (isPrime[i]) : for j in range(i * i, sz, i) : isPrime[j] = False; # Function to return the minimum difference # between any two prime numbers # from the given range [L, R] def minDifference(L, R) : # Find the first prime from the range fst = 0; for i in range(L, R + 1) : if (isPrime[i]) : fst = i; break; # Find the second prime from the range snd = 0; for i in range(fst + 1, R + 1) : if (isPrime[i]) : snd = i; break; # If the number of primes in # the given range is < 2 if (snd == 0) : return -1; # To store the minimum difference between # two consecutive primes from the range diff = snd - fst; # Range left to check for primes left = snd + 1; right = R; # For every integer in the range for i in range(left, right + 1) : # If the current integer is prime if (isPrime[i]) : # If the difference between i # and snd is minimum so far if (i - snd <= diff) : fst = snd; snd = i; diff = snd - fst; return diff; # Driver code if __name__ == "__main__" : # Generate primes sieve(); L = 21; R = 50; print(minDifference(L, R)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int sz = (int) 1e5;
static Boolean []isPrime = new Boolean [sz + 1];
// Function for Sieve of Eratosthenes
static void sieve()
{
for(int i = 2; i< sz + 1; i++)
isPrime[i] = true;
for (int i = 2; i * i <= sz; i++)
{
if (isPrime[i])
{
for (int j = i * i; j < sz; j += i)
{
isPrime[j] = false;
}
}
}
}
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
static int minDifference(int L, int R)
{
// Find the first prime from the range
int fst = 0;
for (int i = L; i <= R; i++)
{
if (isPrime[i])
{
fst = i;
break;
}
}
// Find the second prime from the range
int snd = 0;
for (int i = fst + 1; i <= R; i++)
{
if (isPrime[i])
{
snd = i;
break;
}
}
// If the number of primes in
// the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference between
// two consecutive primes from the range
int diff = snd - fst;
// Range left to check for primes
int left = snd + 1;
int right = R;
// For every integer in the range
for (int i = left; i <= right; i++)
{
// If the current integer is prime
if (isPrime[i])
{
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff)
{
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Driver code
public static void Main(String []args)
{
// Generate primes
sieve();
int L = 21, R = 50;
Console.WriteLine(minDifference(L, R));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
const sz = 1e5;
let isPrime = new Array(sz + 1);
// Function for Sieve of Eratosthenes
function sieve()
{
isPrime.fill(true);
isPrime[0] = isPrime[1] = false;
for(let i = 2; i * i <= sz; i++)
{
if (isPrime[i])
{
for(let j = i * i; j < sz; j += i)
{
isPrime[j] = false;
}
}
}
}
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
function minDifference(L, R)
{
// Find the first prime from the range
let fst = 0;
for(let i = L; i <= R; i++)
{
if (isPrime[i])
{
fst = i;
break;
}
}
// Find the second prime from the range
let snd = 0;
for(let i = fst + 1; i <= R; i++)
{
if (isPrime[i])
{
snd = i;
break;
}
}
// If the number of primes in
// the given range is < 2
if (snd == 0)
return -1;
// To store the minimum difference between
// two consecutive primes from the range
let diff = snd - fst;
// Range left to check for primes
let left = snd + 1;
let right = R;
// For every integer in the range
for(let i = left; i <= right; i++)
{
// If the current integer is prime
if (isPrime[i])
{
// If the difference between i
// and snd is minimum so far
if (i - snd <= diff)
{
fst = snd;
snd = i;
diff = snd - fst;
}
}
}
return diff;
}
// Driver code
// Generate primes
sieve();
let L = 21, R = 50;
document.write(minDifference(L, R));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
2
Complejidad de tiempo: O((R – L) + sqrt(10 5 ))
Espacio Auxiliar: O(10 5 )