Cuente pares de un rango dado cuya suma sea un número primo en ese rango

Dados dos enteros L y R , la tarea es contar el número de pares del rango [L, R] cuya suma es un número primo en el rango [L, R] .

Ejemplos:

Entrada: L = 1, R = 5
Salida: 4
Explicación: Los pares cuya suma es un número primo y en el rango [L, R] son ​​{ (1, 1), (1, 2), (1, 4), (2, 3) }. Por lo tanto, la salida requerida es 4.

Entrada: L = 1, R = 100
Salida: 518

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los pares posibles del rango [1, R ] y, para cada par, verificar si la suma de los elementos del par es un número primo en el rango [L, R] O no. Si se encuentra que es verdadero, entonces incremente el conteo . Finalmente, imprima el valor de count .

Complejidad de Tiempo: O(N 5 / 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:

Si N es un número primo, entonces los pares cuya suma es N son { (1, N – 1), (2, N – 2), ….., piso (N / 2), techo (N / 2) }. Por lo tanto, cuenta total de pares cuya suma es N = N / 2

Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, por ejemplo, cntPairs para almacenar el recuento de pares de modo que la suma de los elementos del par sea un número primo y esté en el rango [L, R] .
  • Inicialice una array, digamos segmentedSieve[] para almacenar todos los números primos en el rango [L, R] usando Sieve of Eratosthenes .
  • Recorra el segmento 
    tedSieve[] usando la variable i y verifique si i es un número primo o no. Si se determina que es cierto, incremente el valor de cntPairs en (i / 2).
  • Finalmente, imprima el valor de cntPairs .

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all prime numbers in range
// [1, lmt] using sieve of Eratosthenes
void simpleSieve(int lmt, vector<int>& prime)
{
 
    // segmentedSieve[i]: Stores if i is
    // a prime number (True) or not (False)
    bool Sieve[lmt + 1];
 
    // Initialize all elements of
    // segmentedSieve[] to false
    memset(Sieve, true, sizeof(Sieve));
 
    // Set 0 and 1 as non-prime
    Sieve[0] = Sieve[1] = false;
 
    // Iterate over the range [2, lmt]
    for (int i = 2; i <= lmt; ++i) {
 
        // If i is a prime number
        if (Sieve[i] == true) {
 
            // Append i into prime
            prime.push_back(i);
 
            // Set all multiple of i non-prime
            for (int j = i * i; j <= lmt; j += i) {
 
                // Update Sieve[j]
                Sieve[j] = false;
            }
        }
    }
}
 
// Function to find all the prime numbers
// in the range [low, high]
vector<bool> SegmentedSieveFn(
    int low, int high)
{
 
    // Stores square root of high + 1
    int lmt = floor(sqrt(high)) + 1;
 
    // Stores all the prime numbers
    // in the range [1, lmt]
    vector<int> prime;
 
    // Find all the prime numbers in
    // the range [1, lmt]
    simpleSieve(lmt, prime);
 
    // Stores count of elements in
    // the range [low, high]
    int n = high - low + 1;
 
    // segmentedSieve[i]: Check if (i - low)
    // is a prime number or not
    vector<bool> segmentedSieve(n + 1, true);
 
    // Traverse the array prime[]
    for (int i = 0; i < prime.size(); i++) {
 
        // Store smallest multiple of prime[i]
        // in the range[low, high]
        int lowLim = floor(low / prime[i])
                     * prime[i];
 
        // If lowLim is less than low
        if (lowLim < low) {
 
            // Update lowLim
            lowLim += prime[i];
        }
 
        // Iterate over all multiples of prime[i]
        for (int j = lowLim; j <= high;
             j += prime[i]) {
 
            // If j not equal to prime[i]
            if (j != prime[i]) {
 
                // Update segmentedSieve[j - low]
                segmentedSieve[j - low] = false;
            }
        }
    }
 
    return segmentedSieve;
}
 
// Function to count the number of pairs
// in the range [L, R] whose sum is a
// prime number in the range [L, R]
int countPairsWhoseSumPrimeL_R(int L, int R)
{
 
    // segmentedSieve[i]: Check if (i - L)
    // is a prime number or not
    vector<bool> segmentedSieve
        = SegmentedSieveFn(L, R);
 
    // Stores count of pairs whose sum of
    // elements is a prime and in range [L, R]
    int cntPairs = 0;
 
    // Iterate over [L, R]
    for (int i = L; i <= R; i++) {
 
        // If (i - L) is a prime
        if (segmentedSieve[i - L]) {
 
            // Update cntPairs
            cntPairs += i / 2;
        }
    }
    return cntPairs;
}
 
// Driver Code
int main()
{
    int L = 1, R = 5;
    cout << countPairsWhoseSumPrimeL_R(L, R);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to find all prime numbers in range
// [1, lmt] using sieve of Eratosthenes
static ArrayList<Integer> simpleSieve(int lmt,
       ArrayList<Integer> prime)
{
     
    // segmentedSieve[i]: Stores if i is
    // a prime number (True) or not (False)
    boolean[] Sieve = new boolean[lmt + 1];
 
    // Initialize all elements of
    // segmentedSieve[] to false
    Arrays.fill(Sieve, true);
 
    // Set 0 and 1 as non-prime
    Sieve[0] = Sieve[1] = false;
 
    // Iterate over the range [2, lmt]
    for(int i = 2; i <= lmt; ++i)
    {
         
        // If i is a prime number
        if (Sieve[i] == true)
        {
             
            // Append i into prime
            prime.add(i);
 
            // Set all multiple of i non-prime
            for(int j = i * i; j <= lmt; j += i)
            {
                 
                // Update Sieve[j]
                Sieve[j] = false;
            }
        }
    }
    return prime;
}
 
// Function to find all the prime numbers
// in the range [low, high]
static boolean[] SegmentedSieveFn(int low, int high)
{
     
    // Stores square root of high + 1
    int lmt = (int)(Math.sqrt(high)) + 1;
 
    // Stores all the prime numbers
    // in the range [1, lmt]
    ArrayList<Integer> prime = new ArrayList<Integer>();
 
    // Find all the prime numbers in
    // the range [1, lmt]
    prime = simpleSieve(lmt, prime);
 
    // Stores count of elements in
    // the range [low, high]
    int n = high - low + 1;
 
    // segmentedSieve[i]: Check if (i - low)
    // is a prime number or not
    boolean[] segmentedSieve = new boolean[n + 1];
    Arrays.fill(segmentedSieve, true);
 
    // Traverse the array prime[]
    for(int i = 0; i < prime.size(); i++)
    {
         
        // Store smallest multiple of prime[i]
        // in the range[low, high]
        int lowLim = (int)(low / prime.get(i)) *
                                 prime.get(i);
 
        // If lowLim is less than low
        if (lowLim < low)
        {
             
            // Update lowLim
            lowLim += prime.get(i);
        }
 
        // Iterate over all multiples of prime[i]
        for(int j = lowLim; j <= high;
                j += prime.get(i))
        {
             
            // If j not equal to prime[i]
            if (j != prime.get(i))
            {
                 
                // Update segmentedSieve[j - low]
                segmentedSieve[j - low] = false;
            }
        }
    }
    return segmentedSieve;
}
 
// Function to count the number of pairs
// in the range [L, R] whose sum is a
// prime number in the range [L, R]
static int countPairsWhoseSumPrimeL_R(int L, int R)
{
     
    // segmentedSieve[i]: Check if (i - L)
    // is a prime number or not
    boolean[] segmentedSieve = SegmentedSieveFn(L, R);
 
    // Stores count of pairs whose sum of
    // elements is a prime and in range [L, R]
    int cntPairs = 0;
 
    // Iterate over [L, R]
    for(int i = L; i <= R; i++)
    {
         
        // If (i - L) is a prime
        if (segmentedSieve[i - L])
        {
             
            // Update cntPairs
            cntPairs += i / 2;
        }
    }
    return cntPairs;
}
 
// Driver Code
public static void main(String[] args)
{
    int L = 1, R = 5;
     
    System.out.println(
        countPairsWhoseSumPrimeL_R(L, R));
}
}
 
// This code is contributed by akhilsaini

Python

# Python program to implement
# the above approach
import math
 
# Function to find all prime numbers in range
# [1, lmt] using sieve of Eratosthenes
def simpleSieve(lmt, prime):
   
    # segmentedSieve[i]: Stores if i is
    # a prime number (True) or not (False)
    Sieve = [True] * (lmt + 1)
 
    # Set 0 and 1 as non-prime
    Sieve[0] = Sieve[1] = False
 
    # Iterate over the range [2, lmt]
    for i in range(2, lmt + 1):
 
        # If i is a prime number
        if (Sieve[i] == True):
 
            # Append i into prime
            prime.append(i)
 
            # Set all multiple of i non-prime
            for j in range(i * i,
              int(math.sqrt(lmt)) + 1, i):
 
                # Update Sieve[j]
                Sieve[j] = false
 
    return prime
 
# Function to find all the prime numbers
# in the range [low, high]
def SegmentedSieveFn(low, high):
 
    # Stores square root of high + 1
    lmt = int(math.sqrt(high)) + 1
 
    # Stores all the prime numbers
    # in the range [1, lmt]
    prime = []
 
    # Find all the prime numbers in
    # the range [1, lmt]
    prime = simpleSieve(lmt, prime)
 
    # Stores count of elements in
    # the range [low, high]
    n = high - low + 1
 
    # segmentedSieve[i]: Check if (i - low)
    # is a prime number or not
    segmentedSieve = [True] * (n + 1)
 
    # Traverse the array prime[]
    for i in range(0, len(prime)):
 
        # Store smallest multiple of prime[i]
        # in the range[low, high]
        lowLim = int(low // prime[i]) * prime[i]
 
        # If lowLim is less than low
        if (lowLim < low):
             
            # Update lowLim
            lowLim += prime[i]
 
            # Iterate over all multiples of prime[i]
            for j in range(lowLim, high + 1, prime[i]):
 
                # If j not equal to prime[i]
                if (j != prime[i]):
                     
                    # Update segmentedSieve[j - low]
                    segmentedSieve[j - low] = False
 
    return segmentedSieve
 
# Function to count the number of pairs
# in the range [L, R] whose sum is a
# prime number in the range [L, R]
def countPairsWhoseSumPrimeL_R(L, R):
 
    # segmentedSieve[i]: Check if (i - L)
    #  is a prime number or not
    segmentedSieve = SegmentedSieveFn(L, R)
 
    # Stores count of pairs whose sum of
    # elements is a prime and in range [L, R]
    cntPairs = 0
 
    # Iterate over [L, R]
    for i in range(L, R + 1):
 
        # If (i - L) is a prime
        if (segmentedSieve[i - L] == True):
 
            # Update cntPairs
            cntPairs += i / 2
 
    return cntPairs
 
# Driver Code
if __name__ == '__main__':
 
    L = 1
    R = 5
     
    print(countPairsWhoseSumPrimeL_R(L, R))
 
# This code is contributed by akhilsaini

C#

// C# program to implement
// the above approach
using System;
using System.Collections;
 
class GFG{
 
// Function to find all prime numbers in range
// [1, lmt] using sieve of Eratosthenes
static ArrayList simpleSieve(int lmt, ArrayList prime)
{
     
    // segmentedSieve[i]: Stores if i is
    // a prime number (True) or not (False)
    bool[] Sieve = new bool[lmt + 1];
 
    // Initialize all elements of
    // segmentedSieve[] to false
    Array.Fill(Sieve, true);
 
    // Set 0 and 1 as non-prime
    Sieve[0] = Sieve[1] = false;
 
    // Iterate over the range [2, lmt]
    for(int i = 2; i <= lmt; ++i)
    {
         
        // If i is a prime number
        if (Sieve[i] == true)
        {
             
            // Append i into prime
            prime.Add(i);
 
            // Set all multiple of i non-prime
            for(int j = i * i; j <= lmt; j += i)
            {
                 
                // Update Sieve[j]
                Sieve[j] = false;
            }
        }
    }
    return prime;
}
 
// Function to find all the prime numbers
// in the range [low, high]
static bool[] SegmentedSieveFn(int low, int high)
{
     
    // Stores square root of high + 1
    int lmt = (int)(Math.Sqrt(high)) + 1;
 
    // Stores all the prime numbers
    // in the range [1, lmt]
    ArrayList prime = new ArrayList();
 
    // Find all the prime numbers in
    // the range [1, lmt]
    prime = simpleSieve(lmt, prime);
 
    // Stores count of elements in
    // the range [low, high]
    int n = high - low + 1;
 
    // segmentedSieve[i]: Check if (i - low)
    // is a prime number or not
    bool[] segmentedSieve = new bool[n + 1];
    Array.Fill(segmentedSieve, true);
 
    // Traverse the array prime[]
    for(int i = 0; i < prime.Count; i++)
    {
         
        // Store smallest multiple of prime[i]
        // in the range[low, high]
        int lowLim = (int)(low / (int)prime[i]) *
                     (int)prime[i];
 
        // If lowLim is less than low
        if (lowLim < low)
        {
             
            // Update lowLim
            lowLim += (int)prime[i];
        }
 
        // Iterate over all multiples of prime[i]
        for(int j = lowLim; j <= high;
                j += (int)prime[i])
        {
             
            // If j not equal to prime[i]
            if (j != (int)prime[i])
            {
                 
                // Update segmentedSieve[j - low]
                segmentedSieve[j - low] = false;
            }
        }
    }
    return segmentedSieve;
}
 
// Function to count the number of pairs
// in the range [L, R] whose sum is a
// prime number in the range [L, R]
static int countPairsWhoseSumPrimeL_R(int L, int R)
{
     
    // segmentedSieve[i]: Check if (i - L)
    // is a prime number or not
    bool[] segmentedSieve = SegmentedSieveFn(L, R);
 
    // Stores count of pairs whose sum of
    // elements is a prime and in range [L, R]
    int cntPairs = 0;
 
    // Iterate over [L, R]
    for(int i = L; i <= R; i++)
    {
         
        // If (i - L) is a prime
        if (segmentedSieve[i - L])
        {
             
            // Update cntPairs
            cntPairs += i / 2;
        }
    }
    return cntPairs;
}
 
// Driver Code
public static void Main()
{
    int L = 1, R = 5;
     
    Console.Write(countPairsWhoseSumPrimeL_R(L, R));
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
 
// Function to find all prime numbers in range
// [1, lmt] using sieve of Eratosthenes
function simpleSieve(lmt, prime)
{
 
    // segmentedSieve[i]: Stores if i is
    // a prime number (True) or not (False)
    let Sieve = new Array(lmt + 1);
 
    // Initialize all elements of
    // segmentedSieve[] to false
    Sieve.fill(true)
 
    // Set 0 and 1 as non-prime
    Sieve[0] = Sieve[1] = false;
 
    // Iterate over the range [2, lmt]
    for (let i = 2; i <= lmt; ++i) {
 
        // If i is a prime number
        if (Sieve[i] == true) {
 
            // Append i into prime
            prime.push(i);
 
            // Set all multiple of i non-prime
            for (let j = i * i; j <= lmt; j += i) {
 
                // Update Sieve[j]
                Sieve[j] = false;
            }
        }
    }
}
 
// Function to find all the prime numbers
// in the range [low, high]
function SegmentedSieveFn(low, high)
{
 
    // Stores square root of high + 1
    let lmt = Math.floor(Math.sqrt(high)) + 1;
 
    // Stores all the prime numbers
    // in the range [1, lmt]
    let prime = new Array();
 
    // Find all the prime numbers in
    // the range [1, lmt]
    simpleSieve(lmt, prime);
 
    // Stores count of elements in
    // the range [low, high]
    let n = high - low + 1;
 
    // segmentedSieve[i]: Check if (i - low)
    // is a prime number or not
    let segmentedSieve = new Array(n + 1).fill(true);
 
    // Traverse the array prime[]
    for (let i = 0; i < prime.length; i++) {
 
        // Store smallest multiple of prime[i]
        // in the range[low, high]
        let lowLim = Math.floor(low / prime[i])
                     * prime[i];
 
        // If lowLim is less than low
        if (lowLim < low) {
 
            // Update lowLim
            lowLim += prime[i];
        }
 
        // Iterate over all multiples of prime[i]
        for (let j = lowLim; j <= high;
             j += prime[i]) {
 
            // If j not equal to prime[i]
            if (j != prime[i]) {
 
                // Update segmentedSieve[j - low]
                segmentedSieve[j - low] = false;
            }
        }
    }
 
    return segmentedSieve;
}
 
// Function to count the number of pairs
// in the range [L, R] whose sum is a
// prime number in the range [L, R]
function countPairsWhoseSumPrimeL_R(L, R)
{
 
    // segmentedSieve[i]: Check if (i - L)
    // is a prime number or not
    let segmentedSieve = SegmentedSieveFn(L, R);
 
    // Stores count of pairs whose sum of
    // elements is a prime and in range [L, R]
    let cntPairs = 0;
 
    // Iterate over [L, R]
    for (let i = L; i <= R; i++) {
 
        // If (i - L) is a prime
        if (segmentedSieve[i - L]) {
 
            // Update cntPairs
            cntPairs += Math.floor(i / 2);
        }
    }
    return cntPairs;
}
 
// Driver Code
 
    let L = 1, R = 5;
    document.write(countPairsWhoseSumPrimeL_R(L, R));
 
    // This code is contributed by gfgking
     
</script>
Producción: 

4

 

Complejidad de tiempo: O((R − L + 1) * log⁡(log⁡(R)) + sqrt(R) * log⁡(log⁡(sqrt(R)))  
Espacio auxiliar: O(R – L + 1 + raíz cuadrada (R))

Publicación traducida automáticamente

Artículo escrito por anmolsingh1899 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 *