Dado un entero k y una array de enteros arr (menos de 10^6), la tarea es encontrar la suma de cada k-ésimo número primo en la array.
Ejemplos:
Entrada: arr[] = {2, 3, 5, 7, 11}, k = 2
Salida: 10
Todos los elementos del arreglo son primos. Entonces, los números primos después de cada intervalo K (es decir, 2) son 3, 7 y su suma es 10.
Entrada: arr[] = {11, 13, 15, 17, 19}, k = 2
Salida: 32
Enfoque simple: recorra la array y encuentre cada número primo K’th en la array y calcule la suma acumulada. De esta manera, tendremos que verificar cada elemento de la array, ya sea que sea primo o no, lo que llevará más tiempo a medida que aumente el tamaño de la array.
Enfoque eficiente: cree un tamiz que almacene si un número es primo o no. Entonces, se puede usar para comparar un número con primo en tiempo O(1). De esta manera, solo tenemos que hacer un seguimiento de cada número primo K’th y mantener la suma acumulada.
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
bool prime[MAX + 1];
void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]"
// and initialize all the entries as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
memset(prime, true, sizeof(prime));
// 0 and 1 are not prime numbers
prime[1] = false;
prime[0] = false;
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;
}
}
}
// compute the answer
void SumOfKthPrimes(int arr[], int n, int k)
{
// count of primes
int c = 0;
// sum of the primes
long long int sum = 0;
// traverse the array
for (int i = 0; i < n; i++) {
// if the number is a prime
if (prime[arr[i]]) {
// increase the count
c++;
// if it is the K'th prime
if (c % k == 0) {
sum += arr[i];
c = 0;
}
}
}
cout << sum << endl;
}
// Driver code
int main()
{
// create the sieve
SieveOfEratosthenes();
int arr[] = { 2, 3, 5, 7, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
SumOfKthPrimes(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
public class GFG {
static int MAX = 1000000;
static boolean prime[] = new boolean[MAX + 1];
static void SieveOfEratosthenes() {
// Create a boolean array "prime[0..n]"
// and initialize all the entries as true.
// A value in prime[i] will finally be false
// if i is Not a prime, else true.
for (int i = 0; i < prime.length; i++) {
prime[i] = true;
}
// 0 and 1 are not prime numbers
prime[1] = false;
prime[0] = false;
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;
}
}
}
}
// compute the answer
static void SumOfKthPrimes(int arr[], int n, int k) {
// count of primes
int c = 0;
// sum of the primes
long sum = 0;
// traverse the array
for (int i = 0; i < n; i++) {
// if the number is a prime
if (prime[arr[i]]) {
// increase the count
c++;
// if it is the K'th prime
if (c % k == 0) {
sum += arr[i];
c = 0;
}
}
}
System.out.println(sum);
}
// Driver code
public static void main(String[] args) {
// create the sieve
SieveOfEratosthenes();
int arr[] = {2, 3, 5, 7, 11};
int n = arr.length;
int k = 2;
SumOfKthPrimes(arr, n, k);
}
}
Python3
# Python3 implementation of the approach MAX = 100000; prime = [True] * (MAX + 1); def SieveOfEratosthenes(): # Create a boolean array "prime[0..n]" # and initialize all the entries # as true. A value in prime[i] will # finally be false if i is Not a prime, # else true. # 0 and 1 are not prime numbers prime[1] = False; prime[0] = False; p = 2; while(p * p <= MAX): # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p i = p * 2; while(i <= MAX): prime[i] = False; i += p; p += 1; # compute the answer def SumOfKthPrimes(arr, n, k): # count of primes c = 0; # sum of the primes sum = 0; # traverse the array for i in range(n): # if the number is a prime if (prime[arr[i]]): # increase the count c+=1; # if it is the K'th prime if (c % k == 0): sum += arr[i]; c = 0; print(sum); # Driver code # create the sieve SieveOfEratosthenes(); arr = [ 2, 3, 5, 7, 11 ]; n = len(arr); k = 2; SumOfKthPrimes(arr, n, k); # This code is contributed by mits
C#
// C# implementation of the approach
class GFG
{
static int MAX = 1000000;
static bool[] prime = new bool[MAX + 1];
static void SieveOfEratosthenes()
{
// Create a boolean array "prime[0..n]"
// and initialize all the entries as true.
// A value in prime[i] will finally be
// false if i is Not a prime, else true.
// 0 and 1 are not prime numbers
prime[1] = false;
prime[0] = false;
for (int p = 2; p * p <= MAX; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == false)
{
// Update all multiples of p
for (int i = p * 2;
i <= MAX; i += p)
prime[i] = true;
}
}
}
// compute the answer
static void SumOfKthPrimes(int[] arr,
int n, int k)
{
// count of primes
int c = 0;
// sum of the primes
long sum = 0;
// traverse the array
for (int i = 0; i < n; i++)
{
// if the number is a prime
if (!prime[arr[i]])
{
// increase the count
c++;
// if it is the K'th prime
if (c % k == 0)
{
sum += arr[i];
c = 0;
}
}
}
System.Console.WriteLine(sum);
}
// Driver code
static void Main()
{
// create the sieve
SieveOfEratosthenes();
int[] arr = new int[] { 2, 3, 5, 7, 11 };
int n = arr.Length;
int k = 2;
SumOfKthPrimes(arr, n, k);
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
$MAX = 100000;
$prime = array_fill(0, $MAX + 1, true);
function SieveOfEratosthenes()
{
global $MAX, $prime;
// Create a boolean array "prime[0..n]"
// and initialize all the entries
// as true. A value in prime[i] will
// finally be false if i is Not a prime,
// else true.
// 0 and 1 are not prime numbers
$prime[1] = false;
$prime[0] = false;
for ($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 ($i = $p * 2;
$i <= $MAX; $i += $p)
$prime[$i] = false;
}
}
}
// compute the answer
function SumOfKthPrimes($arr, $n, $k)
{
global $MAX, $prime;
// count of primes
$c = 0;
// sum of the primes
$sum = 0;
// traverse the array
for ($i = 0; $i < $n; $i++)
{
// if the number is a prime
if ($prime[$arr[$i]])
{
// increase the count
$c++;
// if it is the K'th prime
if ($c % $k == 0)
{
$sum += $arr[$i];
$c = 0;
}
}
}
echo $sum."\n";
}
// Driver code
// create the sieve
SieveOfEratosthenes();
$arr = array( 2, 3, 5, 7, 11 );
$n = sizeof($arr);
$k = 2;
SumOfKthPrimes($arr, $n, $k);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
let MAX = 100000;
let prime = new Array(MAX + 1).fill(true);
function SieveOfEratosthenes() {
// Create a boolean array "prime[0..n]"
// and initialize all the entries
// as true. A value in prime[i] will
// finally be false if i is Not a prime,
// else true.
// 0 and 1 are not prime numbers
prime[1] = false;
prime[0] = false;
for (let 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 (let i = p * 2;
i <= MAX; i += p)
prime[i] = false;
}
}
}
// compute the answer
function SumOfKthPrimes(arr, n, k) {
// count of primes
let c = 0;
// sum of the primes
let sum = 0;
// traverse the array
for (let i = 0; i < n; i++) {
// if the number is a prime
if (prime[arr[i]]) {
// increase the count
c++;
// if it is the K'th prime
if (c % k == 0) {
sum += arr[i];
c = 0;
}
}
}
document.write(sum + "<br>");
}
// Driver code
// create the sieve
SieveOfEratosthenes();
let arr = new Array(2, 3, 5, 7, 11);
let n = arr.length;
let k = 2;
SumOfKthPrimes(arr, n, k);
// This code is contributed by gfgking
</script>
Producción:
10
Complejidad de Tiempo: O(n + MAX 2 ), Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA