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