Dada una array que tiene N elementos. La tarea es verificar si la suma de los elementos primos de la array es primo o no.
Ejemplos:
Input: arr[] = {1, 2, 3}
Output: Yes
As there are two primes in the array i.e. 2 and 3.
So, the sum of prime is 2 + 3 = 5 and 5 is also prime.
Input: arr[] = {2, 3, 2, 2}
Output: No
Enfoque: Primero encuentre el número primo hasta 10^5 usando Sieve . Luego iterar sobre todos los elementos de la array. Si el número es primo, súmalo a la suma. Y finalmente, comprueba si la suma es prima o no. Si es primo, imprime Sí , de lo contrario , No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define ll long long int
#define MAX 100000
using namespace std;
bool prime[MAX];
// Sieve to find prime
void sieve()
{
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = false;
for (int i = 2; i < MAX; i++)
if (prime[i])
for (int j = 2 * i; j < MAX; j += i)
prime[j] = false;
}
// Function to check if the sum of
// prime is prime or not
bool checkArray(int arr[], int n)
{
// find sum of all prime number
ll sum = 0;
for (int i = 0; i < n; i++)
if (prime[arr[i]])
sum += arr[i];
// if sum is prime
// then return yes
if (prime[sum])
return true;
return false;
}
// Driver code
int main()
{
// array of elements
int arr[] = { 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
sieve();
if (checkArray(arr, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
class GFG {
static int MAX =100000;
static boolean prime[] = new boolean[MAX];
// Sieve to find prime
static void sieve()
{
for(int i=0;i<MAX;i++)
{
prime[i] =true;
}
prime[0] = prime[1] = false;
for (int i = 2; i < MAX; i++)
if (prime[i])
for (int j = 2 * i; j < MAX; j += i)
prime[j] = false;
}
// Function to check if the sum of
// prime is prime or not
static boolean checkArray(int arr[], int n)
{
// find sum of all prime number
int sum = 0;
for (int i = 0; i < n; i++)
if (prime[arr[i]])
sum += arr[i];
// if sum is prime
// then return yes
if (prime[sum])
return true;
return false;
}
// Driver code
public static void main (String[] args) {
// array of elements
int arr[] = { 1, 2, 3 };
int n = arr.length;
sieve();
if (checkArray(arr, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by shs..
Python3
# Python3 implementation of above approach
from math import gcd, sqrt
MAX = 100000
prime = [True] * MAX
# Sieve to find prime
def sieve() :
# 0 and 1 are not prime numbers
prime[0] = False
prime[1] = False
for i in range(2, MAX) :
if prime[i] :
for j in range(2**i, MAX, i) :
prime[j] = False
# Function to check if the sum of
# prime is prime or not
def checkArray(arr, n) :
# find sum of all prime number
sum = 0
for i in range(n) :
if prime[arr[i]] :
sum += arr[i]
# if sum is prime
# then return yes
if prime[sum] :
return True
return False
# Driver code
if __name__ == "__main__" :
# list of elements
arr = [1, 2, 3]
n = len(arr)
sieve()
if checkArray(arr, n) :
print("Yes")
else :
print("No")
# This code is contributed by ANKITRAI1
C#
// C# implementation of the above approach
using System;
class GFG
{
static int MAX = 100000;
static bool[] prime = new bool[MAX];
// Sieve to find prime
static void sieve()
{
for(int i = 0; i < MAX; i++)
{
prime[i] = true;
}
prime[0] = prime[1] = false;
for (int i = 2; i < MAX; i++)
if (prime[i])
for (int j = 2 * i;
j < MAX; j += i)
prime[j] = false;
}
// Function to check if the sum of
// prime is prime or not
static bool checkArray(int[] arr, int n)
{
// find sum of all prime number
int sum = 0;
for (int i = 0; i < n; i++)
if (prime[arr[i]])
sum += arr[i];
// if sum is prime
// then return yes
if (prime[sum])
return true;
return false;
}
// Driver code
public static void Main ()
{
// array of elements
int[] arr = new int[] { 1, 2, 3 };
int n = arr.Length;
sieve();
if (checkArray(arr, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the
// above approach
// Sieve to find prime
function sieve()
{
$MAX = 100000;
$prime = array($MAX);
for($i = 0; $i < $MAX; $i++)
{
$prime[$i] = true;
}
$prime[0] = $prime[1] = false;
for ($i = 2; $i < $MAX; $i++)
if ($prime[$i])
for ($j = 2 * $i;
$j < $MAX; $j += $i)
$prime[$j] = false;
}
// Function to check if the sum of
// prime is prime or not
function checkArray($arr, $n)
{
$prime = array(100000);
// find sum of all prime number
$sum = 0;
for ($i = 0; $i < $n; $i++)
if ($prime[$arr[$i]])
$sum += $arr[$i];
// if sum is prime
// then return yes
if ($prime[$sum])
return true;
return false;
}
// Driver code
$arr= array(1, 2, 3);
$n = sizeof($arr);
sieve();
if (checkArray($arr, $n))
echo "Yes";
else
echo "No";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// JavaScript implementation of the
// above approach
// function check whether a number
// is prime or not
function isPrime(n)
{
// Corner case
if (n <= 1)
return 0;
// Check from 2 to n-1
for (let i = 2; i < n; i++)
if (n % i == 0)
return 0;
return 1;
}
var prime = new Array(5);
// Sieve to find prime
function sieve()
{
for(i = 0; i <=5; i++)
{
prime[i] = isPrime(i);
}
}
// Function to check if the sum of
// prime is prime or not
function checkArray(arr, n)
{
// find sum of all prime number
sum = 0;
for (i = 0; i <= n; i++)
if (prime[arr[i]])
sum += arr[i];
// if sum is prime
// then return yes
if (sum)
return 1;
return 0;
}
var arr= [1, 2, 3];
n = 3;
sieve();
if (checkArray(arr, n))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad del tiempo: O(n * log(log n))
Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA