Given an integer ‘k’ and an array of integers ‘arr’ (less than 10^6), the task is to find the product of every K’th prime number in the array.
Examples:
Input: arr = {2, 3, 5, 7, 11}, k = 2
Output: 21
All the elements of the array are prime. So, the prime numbers after every K (i.e. 2) interval are 3, 7 and their product is 21.Input: arr = {41, 23, 12, 17, 18, 19}, k = 2
Output: 437
A simple approach: Traverse the array and find every K’th prime number in the array and calculate the running product. In this way, we’ll have to check every element of the array whether it is prime or not which will take more time as the size of the array increases.
Efficient approach: Create a sieve which will store whether a number is prime or not. Then, it can be used to check a number against prime in O(1) time. In this way, we only have to keep track of every K’th prime number and maintain the running product.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 1000000bool 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 answervoid productOfKthPrimes(int arr[], int n, int k){ // count of primes int c = 0; // product of the primes long long int product = 1; // 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) { product *= arr[i]; c = 0; } } } cout << product << endl;}// Driver codeint main(){ // create the sieve SieveOfEratosthenes(); int n = 5, k = 2; int arr[n] = { 2, 3, 5, 7, 11 }; productOfKthPrimes(arr, n, k); return 0;} |
Java
// Java implementation of the approachclass GFG{static 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. //memset(prime, true, sizeof(prime)); // 0 and 1 are not prime numbers prime[1] = true; prime[0] = true; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == false) { // Update all multiples of p for (int i = p * 2; i <= MAX; i += p) prime[i] = true; } }}// compute the answerstatic void productOfKthPrimes(int arr[], int n, int k){ // count of primes int c = 0; // product of the primes int product = 1; // 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) { product *= arr[i]; c = 0; } } } System.out.println(product);}// Driver codepublic static void main(String[] args){ // create the sieve SieveOfEratosthenes(); int n = 5, k = 2; int[] arr=new int[]{ 2, 3, 5, 7, 11 }; productOfKthPrimes(arr, n, k);}}// This code is contributed by mits |
Python 3
# Python 3 implementation of the approachMAX = 1000000prime = [True]*(MAX + 1)def 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. # 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 answerdef productOfKthPrimes(arr, n, k): # count of primes c = 0 # product of the primes product = 1 # traverse the array for i in range( 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) : product *= arr[i] c = 0 print(product)# Driver codeif __name__ == "__main__": # create the sieve SieveOfEratosthenes() n = 5 k = 2 arr = [ 2, 3, 5, 7, 11 ] productOfKthPrimes(arr, n, k)# This code is contributed by ChitraNayal |
C#
// C# implementation of the approachclass 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. // 0 and 1 are not prime numbers prime[1] = true; prime[0] = true; for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == false) { // Update all multiples of p for (int i = p * 2; i <= MAX; i += p) prime[i] = true; } }}// compute the answerstatic void productOfKthPrimes(int[] arr, int n, int k){ // count of primes int c = 0; // product of the primes int product = 1; // 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) { product *= arr[i]; c = 0; } } } System.Console.WriteLine(product);}// Driver codestatic void Main(){ // create the sieve SieveOfEratosthenes(); int n = 5, k = 2; int[] arr=new int[]{ 2, 3, 5, 7, 11 }; productOfKthPrimes(arr, n, k);}}// This code is contributed by mits |
Javascript
<script>// Javascript implementation of the approachlet MAX = 1000000;let 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 (let 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 (let i = p * 2; i <= MAX; i += p) prime[i] = false; } }}// compute the answerfunction productOfKthPrimes(arr, n, k) { // count of primes let c = 0; // product of the primes let product = 1; // traverse the array for (let 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) { product *= arr[i]; c = 0; } } } document.write(product + "<br>");}// Driver code// create the sieveSieveOfEratosthenes();let n = 5, k = 2;let arr = [2, 3, 5, 7, 11];productOfKthPrimes(arr, n, k);// This code is contributed by gfgking.</script> |
Output
21
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space: O(MAX)
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!
