C++ में एक सरणी में प्रत्येक K'th अभाज्य संख्या का गुणनफल

n अभाज्य संख्याएँ और k युक्त arr[n] सरणी को देखते हुए; कार्य एक सरणी में प्रत्येक k'th अभाज्य संख्या का गुणनफल खोजना है।

जैसे, हमारे पास एक सरणी है arr[] ={3, 5, 7, 11} और k =2 इसलिए प्रत्येक k यानी 5 और 11 के बाद अभाज्य संख्या हमें उनका उत्पाद खोजना होगा जो 5x11 =55 होगा और परिणाम प्रिंट करें आउटपुट के रूप में।

अभाज्य संख्याएं क्या हैं?

एक अभाज्य संख्या एक प्राकृतिक संख्या है जिसे 1 या स्वयं संख्या को छोड़कर किसी अन्य संख्या से विभाजित नहीं किया जा सकता है। कुछ अभाज्य संख्याएँ 2, 3, 5, 7, 11, 13 आदि हैं।

उदाहरण

Input: arr[] = {3, 5, 7, 11, 13} k= 2
Output: 55
Explanation: every 2nd element of the array are 5 and 11; their product will be 55

Input: arr[] = {5, 7, 13, 23, 31} k = 3
Output: 13
Explanation: every 3rd element of an array is 13 so the output will be 13.

उपरोक्त समस्या को हल करने के लिए हम जिस दृष्टिकोण का उपयोग करेंगे -

प्रत्येक k'th तत्व का गुणनफल खोजने के लिए n तत्वों और k की एक इनपुट सरणी लें।
अभाज्य संख्याओं को संग्रहीत करने के लिए एक छलनी बनाएं।
फिर हमें सरणी को पार करना होगा और k'th तत्व प्राप्त करना होगा और इसे प्रत्येक k'th तत्व के लिए उत्पाद चर के साथ पुनरावर्ती रूप से गुणा करना होगा।
उत्पाद प्रिंट करें।

एल्गोरिदम

Start
Step 1-> Define and initialize MAX 1000000
Step 2-> Define bool prime[MAX + 1]
Step 3-> In function createsieve()
   Call memset(prime, true, sizeof(prime));
   Set prime[1] = false
   Set prime[0] = false
   Loop For p = 2 and p * p <= MAX and p++
      If prime[p] == true then,
         For i = p * 2 and i <= MAX and i += p
         Set prime[i] = false
Step 4-> void productOfKthPrimes(int arr[], int n, int k)
   Set c = 0
   Set product = 1
   Loop For i = 0 and i < n and i++
   If prime[arr[i]] then,
      Increment c by 1
      If c % k == 0 {
         Set product = product * arr[i]
         Set c = 0
      Print the product
Step 5-> In function main()
   Call function createsieve()
   Set n = 5, k = 2
   Set arr[n] = { 2, 3, 11, 13, 23 }
   Call productOfKthPrimes(arr, n, k)
Stop

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
bool prime[MAX + 1];
void createsieve() {
   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] == true) {
         // finding all multiples of p
         for (int i = p * 2; i <= MAX; i += p)
         prime[i] = false;
      }
   }
}
// compute the answer
void productOfKthPrimes(int arr[], int n, int k) {
   // count the number of primes
   int c = 0;
   // find the 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]]) {
         c++;
         if (c % k == 0) {
            product *= arr[i];
            c = 0;
         }
      }
   }
   cout << product << endl;
}
//main block
int main() {
   // create the sieve
   createsieve();
   int n = 5, k = 2;
   int arr[n] = { 2, 3, 11, 13, 23 };
   productOfKthPrimes(arr, n, k);  
   return 0;
}