Suma de todos los números primos en un rango dado usando Tamiz de Eratóstenes

Dado un rango [L, R]. La tarea es encontrar la suma de todos los números primos en el rango dado de L a R, ambos inclusive.
Ejemplos :

Input : L = 10, R = 20
Output : Sum = 60
Prime numbers between [10, 20] are:
11, 13, 17, 19
Therefore, sum = 11 + 13 + 17 + 19 = 60

Input : L = 15, R = 25
Output : Sum = 59

Una solución simple es atravesar de L a R, verificar si el número actual es primo. Si es así, añádelo a $sum$ . Finalmente, imprima la suma.
Una solución eficiente es usar la criba de Eratóstenes para encontrar todos los números primos hasta un límite determinado. Luego, calcule una array de suma de prefijos para almacenar la suma hasta cada valor antes del límite. Una vez que tenemos la array de prefijos, solo necesitamos devolver prefijo [R] – prefijo [L-1].
Nota : el prefijo [i] almacenará la suma de todos los números primos del 1 al $i$ .
A continuación se muestra la implementación del enfoque anterior:

C++

// CPP program to find sum of primes
// in range L to R
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 10000;
 
// prefix[i] is going to store sum of primes
// till i (including i).
int prefix[MAX + 1];
 
// Function to build the prefix sum array
void buildPrefix()
{
    // Create a boolean array "prime[0..n]". A
    // value in prime[i] will finally be false
    // if i is Not a prime, else true.
    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
 
    // Build prefix array
    prefix[0] = prefix[1] = 0;
    for (int p = 2; p <= MAX; p++) {
        prefix[p] = prefix[p - 1];
        if (prime[p])
            prefix[p] += p;
    }
}
 
// Function to return sum of prime in range
int sumPrimeRange(int L, int R)
{
    buildPrefix();
 
    return prefix[R] - prefix[L - 1];
}
 
// Driver code
int main()
{
    int L = 10, R = 20;
 
    cout << sumPrimeRange(L, R) << endl;
 
    return 0;
}

Java

// Java program to find sum of primes
// in range L to R
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG{
 
static final int MAX = 10000;
 
// prefix[i] is going to store sum of primes
// till i (including i).
static int prefix[]=new int[MAX + 1];
 
// Function to build the prefix sum array
static void buildPrefix()
{
    // Create a boolean array "prime[0..n]". A
    // value in prime[i] will finally be false
    // if i is Not a prime, else true.
    boolean prime[] = new boolean[MAX + 1];
     
    for(int i = 0; i < MAX+1; i++)
    prime[i] = true;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
 
    // Build prefix array
    prefix[0] = prefix[1] = 0;
    for (int p = 2; p <= MAX; p++) {
        prefix[p] = prefix[p - 1];
        if (prime[p] == true)
            prefix[p] += p;
    }
}
 
// Function to return sum of prime in range
static int sumPrimeRange(int L, int R)
{
    buildPrefix();
 
    return prefix[R] - prefix[L - 1];
}
 
// Driver code
public static void main(String args[])
{
    int L = 10, R = 20;
 
    System.out.println (sumPrimeRange(L, R));
 
}
}

Python3

# Python 3 program to find sum of primes
# in range L to R
from math import sqrt
 
MAX = 10000
 
# prefix[i] is going to store sum of primes
# till i (including i).
prefix = [0 for i in range(MAX + 1)]
 
# Function to build the prefix sum array
def buildPrefix():
     
    # Create a boolean array "prime[0..n]". A
    # value in prime[i] will finally be false
    # if i is Not a prime, else true.
    prime = [True for i in range(MAX + 1)]
 
    for p in range(2,int(sqrt(MAX)) + 1, 1):
         
        # If prime[p] is not changed, then
        # it is a prime
        if (prime[p] == True):
             
            # Update all multiples of p
            for i in range(p * 2, MAX + 1, p):
                prime[i] = False
 
    # Build prefix array
    prefix[0] = 0
    prefix[1] = 0
    for p in range(2, MAX + 1, 1):
        prefix[p] = prefix[p - 1]
        if (prime[p]):
            prefix[p] += p
 
# Function to return sum of prime in range
def sumPrimeRange(L, R):
    buildPrefix()
 
    return prefix[R] - prefix[L - 1]
 
# Driver code
if __name__ == '__main__':
    L = 10
    R = 20
    print(sumPrimeRange(L, R))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find sum of
// primes in range L to R
using System;
class GFG
{
 
static int MAX = 10000;
 
// prefix[i] is going to
// store sum of primes
// till i (including i).
static int []prefix = new int[MAX + 1];
 
// Function to build the
// prefix sum array
static void buildPrefix()
{
    // Create a boolean array "prime[0..n]".
    // A value in prime[i] will finally
    // be false if i is Not a prime,
    // else true.
    bool []prime = new bool[MAX + 1];
     
    for(int i = 0; i < MAX+1; i++)
    prime[i] = true;
 
    for (int p = 2; p * p <= MAX; p++)
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
 
            // Update all multiples of p
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
 
    // Build prefix array
    prefix[0] = prefix[1] = 0;
    for (int p = 2; p <= MAX; p++)
    {
        prefix[p] = prefix[p - 1];
        if (prime[p] == true)
            prefix[p] += p;
    }
}
 
// Function to return sum
// of prime in range
static int sumPrimeRange(int L, int R)
{
    buildPrefix();
 
    return prefix[R] - prefix[L - 1];
}
 
// Driver code
public static void Main()
{
    int L = 10, R = 20;
 
    Console.WriteLine(sumPrimeRange(L, R));
}
}
 
// This code is contributed
// by anuj_67

Javascript

<script>
// Jacascript program to find sum of primes
 
MAX = 10000;
 
// prefix[i] is going to store sum of primes
// till i (including i).
prefix = new Array(MAX + 1);
 
// Function to build the prefix sum array
function buildPrefix()
{
    // Create a boolean array "prime[0..n]". A
    // value in prime[i] will finally be false
    // if i is Not a prime, else true.
    prime = new Array(MAX + 1);
    prime.fill(true);
 
    for (var p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then
        // it is a prime
        if (prime[p] == true) {
 
            // Update all multiples of p
            for (var i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
 
    // Build prefix array
    prefix[0] = prefix[1] = 0;
    for (var p = 2; p <= MAX; p++) {
        prefix[p] = prefix[p - 1];
        if (prime[p])
            prefix[p] += p;
    }
}
 
// Function to return sum of prime in range
function sumPrimeRange(L, R)
{
    buildPrefix();
    return prefix[R] - prefix[L - 1];
}
 
var L = 10, R = 20;
document.write( sumPrimeRange(L, R) + "<br>");
 
// This code is contributed by SoumikMondal
</script>

Producción:

La complejidad del tiempo y el espacio será la misma que en Sieve Of Eratosthenes

Complejidad de tiempo: n*log(log(n)) (donde n = MAX, porque estamos construyendo un tamiz hasta ese límite)

Espacio Auxiliar : O(n)

Publicación traducida automáticamente

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