Dadas K arrays donde la primera array contiene el primer número primo, la segunda array contiene los siguientes 2 números primos y la tercera array contiene los siguientes 3 números primos y así sucesivamente. La tarea es encontrar la suma de los números primos en el K -ésimo arreglo.
Ejemplos:
Entrada: K = 3
Salida: 31
arr1[] = {2}
arr[] = {3, 5}
arr[] = {7, 11, 13}
7 + 11 + 13 = 31
Entrada: K = 2
Salida: 8
Enfoque: La criba de Eratóstenes se puede utilizar para encontrar todos los primos hasta el elemento requerido. Y el conteo de números primos en las arrays de 1 a K – 1 será cnt = 1 + 2 + 3 + … + (K – 1) = (K * (K – 1)) / 2 . Ahora, a partir del (cnt + 1) número primo de la array de tamices, comience a sumar todos los números primos hasta que se sumen exactamente K números primos y luego imprima la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// To store whether a number is prime or not
bool prime[MAX];
// Function for Sieve of Eratosthenes
void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
for (int i = 0; i < MAX; 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]) {
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the sum of
// primes in the Kth array
int sumPrime(int k)
{
// Update vector v to store all the
// prime numbers upto MAX
SieveOfEratosthenes();
vector<int> v;
for (int i = 2; i < MAX; i++) {
if (prime[i])
v.push_back(i);
}
// To store the sum of primes
// in the kth array
int sum = 0;
// Count of primes which are in
// the arrays from 1 to k - 1
int skip = (k * (k - 1)) / 2;
// k is the number of primes
// in the kth array
while (k > 0) {
sum += v[skip];
skip++;
// A prime has been
// added to the sum
k--;
}
return sum;
}
// Driver code
int main()
{
int k = 3;
cout << sumPrime(k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 1000000;
// To store whether a number is prime or not
static boolean []prime = new boolean[MAX];
// Function for Sieve of Eratosthenes
static void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
for (int i = 0; i < MAX; 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])
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the sum of
// primes in the Kth array
static int sumPrime(int k)
{
// Update vector v to store all the
// prime numbers upto MAX
SieveOfEratosthenes();
Vector<Integer> v = new Vector<>();
for (int i = 2; i < MAX; i++)
{
if (prime[i])
v.add(i);
}
// To store the sum of primes
// in the kth array
int sum = 0;
// Count of primes which are in
// the arrays from 1 to k - 1
int skip = (k * (k - 1)) / 2;
// k is the number of primes
// in the kth array
while (k > 0)
{
sum += v.get(skip);
skip++;
// A prime has been
// added to the sum
k--;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int k = 3;
System.out.println(sumPrime(k));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach from math import sqrt MAX = 1000000 # Create a boolean array "prime[0..n]" and # initialize all entries it as true. # A value in prime[i] will finally be false # if i is Not a prime, else true. prime = [True] * MAX # Function for Sieve of Eratosthenes def SieveOfEratosthenes() : for p in range(2, int(sqrt(MAX)) + 1) : # If prime[p] is not changed # then it is a prime if (prime[p]) : # Update all multiples of p greater than or # equal to the square of it # numbers which are multiple of p and are # less than p^2 are already been marked. for i in range(p * p, MAX, p) : prime[i] = False; # Function to return the sum of # primes in the Kth array def sumPrime(k) : # Update vector v to store all the # prime numbers upto MAX SieveOfEratosthenes(); v = []; for i in range(2, MAX) : if (prime[i]) : v.append(i); # To store the sum of primes # in the kth array sum = 0; # Count of primes which are in # the arrays from 1 to k - 1 skip = (k * (k - 1)) // 2; # k is the number of primes # in the kth array while (k > 0) : sum += v[skip]; skip += 1; # A prime has been # added to the sum k -= 1; return sum; # Driver code if __name__ == "__main__" : k = 3; print(sumPrime(k)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 1000000;
// To store whether a number is prime or not
static bool []prime = new bool[MAX];
// Function for Sieve of Eratosthenes
static void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
for (int i = 0; i < MAX; 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])
{
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (int i = p * p; i < MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the sum of
// primes in the Kth array
static int sumPrime(int k)
{
// Update vector v to store all the
// prime numbers upto MAX
SieveOfEratosthenes();
List<int> v = new List<int>();
for (int i = 2; i < MAX; i++)
{
if (prime[i])
v.Add(i);
}
// To store the sum of primes
// in the kth array
int sum = 0;
// Count of primes which are in
// the arrays from 1 to k - 1
int skip = (k * (k - 1)) / 2;
// k is the number of primes
// in the kth array
while (k > 0)
{
sum += v[skip];
skip++;
// A prime has been
// added to the sum
k--;
}
return sum;
}
// Driver code
public static void Main(String[] args)
{
int k = 3;
Console.WriteLine(sumPrime(k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach\
const MAX = 1000000;
// To store whether a number is prime or not
let prime = new Array(MAX);
// Function for Sieve of Eratosthenes
function SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
for (let i = 0; i < MAX; i++)
prime[i] = true;
for (let p = 2; p * p < MAX; p++) {
// If prime[p] is not changed then it is a prime
if (prime[p]) {
// Update all multiples of p greater than or
// equal to the square of it
// numbers which are multiple of p and are
// less than p^2 are already been marked.
for (let i = p * p; i < MAX; i += p)
prime[i] = false;
}
}
}
// Function to return the sum of
// primes in the Kth array
function sumPrime(k)
{
// Update vector v to store all the
// prime numbers upto MAX
SieveOfEratosthenes();
let v = [];
for (let i = 2; i < MAX; i++) {
if (prime[i])
v.push(i);
}
// To store the sum of primes
// in the kth array
let sum = 0;
// Count of primes which are in
// the arrays from 1 to k - 1
let skip = parseInt((k * (k - 1)) / 2);
// k is the number of primes
// in the kth array
while (k > 0) {
sum += v[skip];
skip++;
// A prime has been
// added to the sum
k--;
}
return sum;
}
// Driver code
let k = 3;
document.write(sumPrime(k));
</script>
Producción:
31
Complejidad de tiempo: O (MAX)
Espacio Auxiliar: O(MAX)