Dado un entero D , la tarea es encontrar la suma de todos los números primos cuyo número de dígitos sea menor o igual que D .
Ejemplos:
Entrada: D = 2
Salida: 1060
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97 son
los números primos que tienen dígitos menores o iguales
a 2 y la suma de estos números primos es 1060.Entrada: D = 3
Salida: 76127
Enfoque: genere todos los números primos usando la criba de Eratóstenes hasta el número máximo de dígitos D 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++14
// C++ implementation of the approach
#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 d-digits
int maxVal = pow(10, 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 = 3;
cout << sumPrime(d);
return 0;
}
Java
// Java implementation of the approach
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)
{
int i;
// Maximum number of d-digits
int maxVal = (int)Math.pow(10, d) - 1;
// Sieve of Eratosthenes
boolean prime[] = new boolean[maxVal + 1];
for(i = 0; i < maxVal + 1; i++)
prime[i] = true;
sieve(prime, maxVal);
// To store the required sum
int sum = 0;
for (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 = 3;
System.out.println(sumPrime(d));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach from math import sqrt # Function for Sieve of Eratosthenes def sieve(prime, n) : prime[0] = False; prime[1] = False; for p in range(2, int(sqrt(n)) + 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 d-digits maxVal = (10 ** d) - 1; # Sieve of Eratosthenes prime = [True] * (maxVal + 1); sieve(prime, maxVal); # To store the required sum sum = 0; for i in range(2, maxVal + 1) : # If current element is prime if (prime[i]) : sum += i; return sum; # Driver code if __name__ == "__main__" : d = 3; print(sumPrime(d)); # This code is contributed by kanugargng
C#
// C# implementation of the above approach
using System;
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)
{
int i;
// Maximum number of d-digits
int maxVal = (int)Math.Pow(10, d) - 1;
// Sieve of Eratosthenes
Boolean []prime = new Boolean[maxVal + 1];
for(i = 0; i < maxVal + 1; i++)
prime[i] = true;
sieve(prime, maxVal);
// To store the required sum
int sum = 0;
for (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 = 3;
Console.WriteLine(sumPrime(d));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function for Sieve of Eratosthenes
function sieve(prime, n)
{
prime[0] = false;
prime[1] = false;
for(let p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for(let 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 d-digits
let maxVal = Math.pow(10, d) - 1;
// Sieve of Eratosthenes
let prime = new Array(maxVal + 1);
prime.fill(true)
sieve(prime, maxVal);
// To store the required sum
let sum = 0;
for(let i = 2; i <= maxVal; i++)
{
// If current element is prime
if (prime[i])
{
sum += i;
}
}
return sum;
}
// Driver code
let d = 3;
document.write(sumPrime(d));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
76127