Suma de todos los números primos con la posición máxima del bit establecido ≤ D

Dado un entero D , la tarea es encontrar la suma de todos los números primos cuya posición máxima de bits establecidos (el bit establecido más alejado de la derecha) es menor o igual que D . 
Nota: 2 en binario es 10 y la posición de bit máxima establecida es 2. 7 en binario es 111, la posición de bit máxima establecida es 3.

Ejemplos:  

Entrada: D = 3 
Salida: 17 
2, 3, 5 y 7 son los únicos primos 
que cumplen la condición dada.
Entrada: D = 8 
Salida: 6081  

Enfoque: El número máximo que satisface la condición dada es 2 ^D – 1 . Por lo tanto, genere todos los números primos usando la criba de Eratóstenes hasta 2 ^D – 1 y luego encuentre la suma de todos los números primos en el mismo rango.

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

// C++
#include <bits/stdc++.h>
using namespace std;
 
// Function for Sieve of Eratosthenes
void sieve(bool prime[], int n)
{
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the sum of
// the required prime numbers
int sumPrime(int d)
{
 
    // Maximum number of the required range
    int maxVal = pow(2, d) - 1;
 
    // Sieve of Eratosthenes
    bool prime[maxVal + 1];
    memset(prime, true, sizeof(prime));
    sieve(prime, maxVal);
 
    // To store the required sum
    int sum = 0;
 
    for (int i = 2; i <= maxVal; i++) {
 
        // If current element is prime
        if (prime[i]) {
            sum += i;
        }
    }
 
    return sum;
}
 
// Driver code
int main()
{
    int d = 8;
 
    cout << sumPrime(d);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function for Sieve of Eratosthenes
static void sieve(boolean prime[], int n)
{
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p;
                     i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the sum of
// the required prime numbers
static int sumPrime(int d)
{
 
    // Maximum number of the required range
    int maxVal = (int) (Math.pow(2, d) - 1);
 
    // Sieve of Eratosthenes
    boolean []prime = new boolean[maxVal + 1];
    Arrays.fill(prime, true);
    sieve(prime, maxVal);
 
    // To store the required sum
    int sum = 0;
 
    for (int i = 2; i <= maxVal; i++)
    {
 
        // If current element is prime
        if (prime[i])
        {
            sum += i;
        }
    }
    return sum;
}
 
// Driver code
public static void main(String[] args)
{
    int d = 8;
 
    System.out.println(sumPrime(d));
}
}
 
// This code is contributed by PrinciRaj1992

# Python 3 implementation of the approach
from math import sqrt, pow
 
# Function for Sieve of Eratosthenes
def sieve(prime, n):
    prime[0] = False
    prime[1] = False
    for p in range(2, int(sqrt(n)) + 1, 1):
        if (prime[p] == True):
            for i in range(p * p, n + 1, p):
                prime[i] = False
 
# Function to return the sum of
# the required prime numbers
def sumPrime(d):
     
    # Maximum number of the required range
    maxVal = int(pow(2, d)) - 1;
 
    # Sieve of Eratosthenes
    prime = [True for i in range(maxVal + 1)]
     
    sieve(prime, maxVal)
 
    # To store the required sum
    sum = 0
 
    for i in range(2, maxVal + 1, 1):
         
        # If current element is prime
        if (prime[i]):
            sum += i
 
    return sum
 
# Driver code
if __name__ == '__main__':
    d = 8
 
    print(sumPrime(d))
 
# This code is contributed by Surendra_Gangwar

// C# implementation of the approach
using System;
using System.Linq;
 
class GFG
{
 
// Function for Sieve of Eratosthenes
static void sieve(Boolean []prime, int n)
{
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p;
                    i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the sum of
// the required prime numbers
static int sumPrime(int d)
{
 
    // Maximum number of the required range
    int maxVal = (int) (Math.Pow(2, d) - 1);
 
    // Sieve of Eratosthenes
    Boolean []prime = new Boolean[maxVal + 1];
     
    for (int i = 0; i <= maxVal; i++)
        prime.SetValue(true,i);
    sieve(prime, maxVal);
 
    // To store the required sum
    int sum = 0;
 
    for (int i = 2; i <= maxVal; i++)
    {
 
        // If current element is prime
        if (prime[i])
        {
            sum += i;
        }
    }
    return sum;
}
 
// Driver code
public static void Main(String[] args)
{
    int d = 8;
 
    Console.WriteLine(sumPrime(d));
}
}
 
// This code is contributed by 29AjayKumar

<script>
//Javascript implementation of the approach
 
// Function for Sieve of Eratosthenes
function sieve(prime, n)
{
    prime[0] = false;
    prime[1] = false;
    for (var p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (var i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to return the sum of
// the required prime numbers
function sumPrime(d)
{
 
    // Maximum number of the required range
    var maxVal = Math.pow(2, d) - 1;
 
    // Sieve of Eratosthenes
    var prime = new Array(maxVal + 1);
    prime.fill(true);
    sieve(prime, maxVal);
 
    // To store the required sum
    var sum = 0;
 
    for (var i = 2; i <= maxVal; i++) {
 
        // If current element is prime
        if (prime[i]) {
            sum += i;
        }
    }
 
    return sum;
}
 
var d = 8;
 document.write(  sumPrime(d));
 
 
 
//This code is contributed by SoumikMondal
</script>

6081

Complejidad del tiempo: O(sqrt(2 ^d ))

Espacio Auxiliar: O(2 ^d )