Suma de cada número primo K’th en una array

Dada una array de números enteros (menos de 10^6), la tarea es encontrar la suma de todos los números primos que aparecen después de cada (k-1) número primo, 
es decir, cada K-ésimo número primo de la array.
Ejemplos: 
 

Input : Array : 2, 3, 5, 7, 11 ; n=5; k=2
Output : Sum = 10
Explanation: All the elements of the array are prime. So,
the prime numbers after every K intervals are 3, 7 and their sum is 10.   


Input : Array : 41, 23, 12, 17, 18, 19 ; n=6; k=2
Output : Sum = 42

Un enfoque simple 
Tenemos que atravesar la array y encontrar los números primos después de cada (k-1) números primos. 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 
Crearemos un tamiz que almacenará 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 solve(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 n = 5, k = 2;
 
    int arr[n] = { 2, 3, 5, 7, 11 };
 
    solve(arr, n, k);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
       
    static final 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<=MAX;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 solve(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 n = 5, k = 2;
     
        int []arr = { 2, 3, 5, 7, 11 };
     
        solve(arr, n, k);
     
    }
 
}

Python3

# Python3 implementation of the approach
def SieveOfEratosthenes():
 
    # 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] == True:
 
            # Update all multiples of p
            for i in range(p * 2, MAX + 1, p):
                prime[i] = False
         
        p += 1
 
# Compute the answer
def solve(arr, n, k):
 
    # count of primes
    c = 0
 
    # sum of the primes
    Sum = 0
 
    # Traverse the array
    for i in range(0, 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
if __name__ == "__main__":
 
    MAX = 1000000
    prime = [True] * (MAX + 1)
 
    # Create the sieve
    SieveOfEratosthenes()
 
    n, k = 5, 2
    arr = [2, 3, 5, 7, 11]
 
    solve(arr, n, k)
     
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
 
using System;
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.
        for(int i=0;i<=MAX;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 solve(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;
                }
            }
        }
        Console.WriteLine(sum);
    }
     
    // Driver code
    public static void Main()
    {
     
        // create the sieve
        SieveOfEratosthenes();
     
        int n = 5, k = 2;
     
        int []arr = { 2, 3, 5, 7, 11 };
     
        solve(arr, n, k);
     
    }
 
}

Javascript

<script>
 
// Javascript program to find next
// greater number than N
 
MAX = 1000000;
prime = new Array(MAX + 1);
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.
    prime.fill(true);
     
    // 0 and 1 are not prime numbers
    prime[1] = false;
    prime[0] = false;
 
    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;
        }
    }
}
 
// compute the answer
function solve(arr, n, k)
{
    // count of primes
    var c = 0;
 
    // sum of the primes
    var sum = 0;
 
    // traverse the array
    for (var 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>")
}
 
SieveOfEratosthenes();
var n = 5, k = 2;
var arr = [ 2, 3, 5, 7, 11 ];
solve(arr, n, k);
         
// This code is contributed by SoumikMondal
 
</script>
Producción: 

10

 

Publicación traducida automáticamente

Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *