Given an array having N elements. The task is to check if the sum of prime elements of the array is prime or not.
Examples:
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
Approach: First find prime number up to 10^5 using Sieve. Then iterate over all elements of the array. If the number is prime then add it to sum. And finally, check whether the sum is prime or not. If prime then prints Yes otherwise No.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>#define ll long long int#define MAX 100000using namespace std;bool prime[MAX];// Sieve to find primevoid 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 notbool 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 codeint 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 approachimport java.io.*;class GFG { static int MAX =100000;static boolean prime[] = new boolean[MAX];// Sieve to find primestatic 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 notstatic 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 approachfrom math import gcd, sqrtMAX = 100000prime = [True] * MAX# Sieve to find primedef 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 notdef 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 codeif __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 approachusing System;class GFG{static int MAX = 100000;static bool[] prime = new bool[MAX];// Sieve to find primestatic 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 notstatic 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 codepublic 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 primefunction 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 notfunction 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 notfunction 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 primefunction sieve(){ for(i = 0; i <=5; i++) { prime[i] = isPrime(i); }}// Function to check if the sum of// prime is prime or notfunction 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> |
Output
Yes
Complexity Analysis:
- Time Complexity: O(n * log(log n))
- Auxiliary Space: O(MAX)
Approach 2:Without Sieve Array(No Extra Space)
The previous code used a sieve to pre-compute all primes up to a certain limit, and then used this pre-computed information to check if the sum of primes in the array is also prime. This approach requires extra memory to store the sieve array and runs in O(MAX*log(log(MAX))) time complexity, where MAX is the limit up to which primes are computed.
The new code optimizes the previous approach by checking if each number in the array is prime as we go through it. Instead of pre-computing all primes up to a certain limit, we only need to check if each number is divisible by any prime less than or equal to its square root. This approach does not require extra memory to store the sieve array.
C++
#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to check if a number is primebool isPrime(int n){ if (n <= 1) return false; for (int i = 2; i*i <= n; i++) if (n % i == 0) return false; return true;}// Function to check if the sum of// prime is prime or notbool checkArray(int arr[], int n){ // find sum of all prime number ll sum = 0; for (int i = 0; i < n; i++) if (isPrime(arr[i])) sum += arr[i]; // if sum is prime // then return yes if (isPrime(sum)) return true; return false;}// Driver codeint main(){ // array of elements int arr[] = { 2,3,2,2 }; int n = sizeof(arr) / sizeof(arr[0]); if (checkArray(arr, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
/*package whatever //do not write package name here */import java.lang.Math;public class Main { // Function to check if a number is prime static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } // 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 (isPrime(arr[i])) { sum += arr[i]; } } // if sum is prime then return true if (isPrime(sum)) { return true; } return false; } // Driver code public static void main(String[] args) { int[] arr = {1, 2, 3}; int n = arr.length; if (checkArray(arr, n)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
# Function to check if a number is primedef isPrime(n): if n <= 1: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True# Function to check if the sum of# prime is prime or notdef checkArray(arr, n): # find sum of all prime number sum = 0 for i in range(n): if isPrime(arr[i]): sum += arr[i] # if sum is prime # then return yes if isPrime(sum): return True return False# Driver codearr = [1, 2, 3]n = len(arr)if checkArray(arr, n): print("Yes")else: print("No") |
C#
using System;public class MainClass { // Function to check if a number is prime static bool IsPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } // 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 (IsPrime(arr[i])) { sum += arr[i]; } } // if sum is prime then return true if (IsPrime(sum)) { return true; } return false; } // Driver code public static void Main() { int[] arr = {1, 2, 3}; int n = arr.Length; if (CheckArray(arr, n)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
// Function to check if a number is primefunction isPrime(n) { if (n <= 1) { return false; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false; } } return true;}// Function to check if the sum of// prime is prime or notfunction checkArray(arr, n) { // find sum of all prime number let sum = 0; for (let i = 0; i < n; i++) { if (isPrime(arr[i])) { sum += arr[i]; } } // if sum is prime // then return yes if (isPrime(sum)) { return true; } return false;}// Driver codeconst arr = [1, 2, 3];const n = arr.length;if (checkArray(arr, n)) { console.log("Yes");} else { console.log("No");}// Contributed by adityasha4x71 |
Output
Yes
Complexity Analysis:
Time Complexity: O(n * sqrt(max(arr))).
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
