Given K arrays where the first array contains the first prime number, the second array contains the next 2 primes and the third array contains the next 3 primes and so on. The task is to find the sum of primes in the Kth array.
Examples:
Input: K = 3
Output: 31
arr1[] = {2}
arr[] = {3, 5}
arr[] = {7, 11, 13}
7 + 11 + 13 = 31
Input: K = 2
Output: 8
Approach: Sieve of Eratosthenes can be used to find all the prime upto the required element. And the count of prime numbers in the arrays from 1 to K – 1 will be cnt = 1 + 2 + 3 + … + (K – 1) = (K * (K – 1)) / 2. Now, starting from the (cnt + 1)th prime from the sieve array, start adding all the primes until exactly K primes are added then print the sum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 1000000 // To store whether a number is prime or not bool prime[MAX]; // Function for Sieve of Eratosthenes void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it 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 ; for ( int p = 2; p * p < MAX; p++) { // If prime[p] is not changed then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to return the sum of // primes in the Kth array int sumPrime( int k) { // Update vector v to store all the // prime numbers upto MAX SieveOfEratosthenes(); vector< int > v; for ( int i = 2; i < MAX; i++) { if (prime[i]) v.push_back(i); } // To store the sum of primes // in the kth array int sum = 0; // Count of primes which are in // the arrays from 1 to k - 1 int skip = (k * (k - 1)) / 2; // k is the number of primes // in the kth array while (k > 0) { sum += v[skip]; skip++; // A prime has been // added to the sum k--; } return sum; } // Driver code int main() { int k = 3; cout << sumPrime(k); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { static int MAX = 1000000 ; // To store whether a number is prime or not static boolean []prime = new boolean [MAX]; // Function for Sieve of Eratosthenes static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and // initialize all entries it 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 ; for ( int p = 2 ; p * p < MAX; p++) { // If prime[p] is not changed // then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to return the sum of // primes in the Kth array static int sumPrime( int k) { // Update vector v to store all the // prime numbers upto MAX SieveOfEratosthenes(); Vector<Integer> v = new Vector<>(); for ( int i = 2 ; i < MAX; i++) { if (prime[i]) v.add(i); } // To store the sum of primes // in the kth array int sum = 0 ; // Count of primes which are in // the arrays from 1 to k - 1 int skip = (k * (k - 1 )) / 2 ; // k is the number of primes // in the kth array while (k > 0 ) { sum += v.get(skip); skip++; // A prime has been // added to the sum k--; } return sum; } // Driver code public static void main(String[] args) { int k = 3 ; System.out.println(sumPrime(k)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach from math import sqrt MAX = 1000000 # Create a boolean array "prime[0..n]" and # initialize all entries it as true. # A value in prime[i] will finally be false # if i is Not a prime, else true. prime = [ True ] * MAX # Function for Sieve of Eratosthenes def SieveOfEratosthenes() : for p in range ( 2 , int (sqrt( MAX )) + 1 ) : # If prime[p] is not changed # then it is a prime if (prime[p]) : # Update all multiples of p greater than or # equal to the square of it # numbers which are multiple of p and are # less than p^2 are already been marked. for i in range (p * p, MAX , p) : prime[i] = False ; # Function to return the sum of # primes in the Kth array def sumPrime(k) : # Update vector v to store all the # prime numbers upto MAX SieveOfEratosthenes(); v = []; for i in range ( 2 , MAX ) : if (prime[i]) : v.append(i); # To store the sum of primes # in the kth array sum = 0 ; # Count of primes which are in # the arrays from 1 to k - 1 skip = (k * (k - 1 )) / / 2 ; # k is the number of primes # in the kth array while (k > 0 ) : sum + = v[skip]; skip + = 1 ; # A prime has been # added to the sum k - = 1 ; return sum ; # Driver code if __name__ = = "__main__" : k = 3 ; print (sumPrime(k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static int MAX = 1000000; // To store whether a number is prime or not static bool []prime = new bool [MAX]; // Function for Sieve of Eratosthenes static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and // initialize all entries it 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 ; for ( int p = 2; p * p < MAX; p++) { // If prime[p] is not changed // then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to return the sum of // primes in the Kth array static int sumPrime( int k) { // Update vector v to store all the // prime numbers upto MAX SieveOfEratosthenes(); List< int > v = new List< int >(); for ( int i = 2; i < MAX; i++) { if (prime[i]) v.Add(i); } // To store the sum of primes // in the kth array int sum = 0; // Count of primes which are in // the arrays from 1 to k - 1 int skip = (k * (k - 1)) / 2; // k is the number of primes // in the kth array while (k > 0) { sum += v[skip]; skip++; // A prime has been // added to the sum k--; } return sum; } // Driver code public static void Main(String[] args) { int k = 3; Console.WriteLine(sumPrime(k)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach\ const MAX = 1000000; // To store whether a number is prime or not let prime = new Array(MAX); // Function for Sieve of Eratosthenes function SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. for (let i = 0; i < MAX; i++) prime[i] = true ; for (let p = 2; p * p < MAX; p++) { // If prime[p] is not changed then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (let i = p * p; i < MAX; i += p) prime[i] = false ; } } } // Function to return the sum of // primes in the Kth array function sumPrime(k) { // Update vector v to store all the // prime numbers upto MAX SieveOfEratosthenes(); let v = []; for (let i = 2; i < MAX; i++) { if (prime[i]) v.push(i); } // To store the sum of primes // in the kth array let sum = 0; // Count of primes which are in // the arrays from 1 to k - 1 let skip = parseInt((k * (k - 1)) / 2); // k is the number of primes // in the kth array while (k > 0) { sum += v[skip]; skip++; // A prime has been // added to the sum k--; } return sum; } // Driver code let k = 3; document.write(sumPrime(k)); </script> |
31
Time Complexity: O(MAX)
Auxiliary Space: O(MAX)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!