n প্রাইম নম্বর ধারণকারী একটি অ্যারে arr[n] এবং k দেওয়া আছে; কাজ হল অ্যারেতে প্রতিটি k-তম প্রাইম নম্বরের গুণফল বের করা।
যেমন, আমাদের একটি অ্যারে arr[] = {3, 5, 7, 11} এবং k = 2 আছে, তাহলে প্রতিটি k অর্থাৎ 5 এবং 11-র গুণফল বের করতে হবে যেটি 5x11 = 55 এবং আউটপুট হিসেবে প্রিন্ট করা হবে।
প্রাইম নম্বর কী?
প্রাইম নম্বর হল একটি প্রাকৃতিক সংখ্যা যা ১ এবং নিজস্ব নম্বর বাদে অন্য কোনো সংখ্যা দিয়ে বিভাজ্য নয়। কিছু প্রাইম নম্বর হল 2, 3, 5, 7, 11, 13 ইত্যাদি।
উদাহরণ
Input: arr[] = {3, 5, 7, 11, 13} k=2
Output: 55
Explanation: অ্যারেতে প্রতিটি ২য় উপাদান হল 5 এবং 11; তাদের গুণফল 55
Input: arr[] = {5, 7, 13, 23, 31} k=3
Output: 13
Explanation: অ্যারেতে প্রতিটি ৩য় উপাদান হল 13 তাই আউটপুট 13।
সমাধানের পদ্ধতি:
- n উপাদানের ইনপুট অ্যারে এবং k নিন প্রতি k-তম উপাদানের গুণফল বের করার জন্য।
- প্রাইম নম্বর সংরক্ষণের জন্য একটি সিভ (sieve) তৈরি করুন।
- তারপর অ্যারে ট্রভার্স করে k-তম উপাদান বের করুন এবং প্রোডাক্ট ভেরিয়েবলের সাথে গুণ করুন প্রতিটি k-তম উপাদানের জন্য।
- গুণফল প্রিন্ট করুন।
অ্যালগরিদম
Start
Step 1-> MAX 1000000 ডিক্লেয়ার ও আরম্ভ
Step 2-> bool prime[MAX+1] ডিক্লেয়ার
Step 3-> createsieve() ফাংশনে:
memset(prime, true, sizeof(prime))
prime[1] = false, prime[0] = false
Loop p=2 to p*p<=MAX:
If prime[p] == true:
For i=p*2 to MAX step p: prime[i] = false
Step 4-> productOfKthPrimes(int arr[], int n, int k):
c = 0, product = 1
Loop i=0 to n-1:
If prime[arr[i]]: c++
If c%k == 0: product *= arr[i], c = 0
Print product
Step 5-> main():
Call createsieve()
n=5, k=2, 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));
prime[1] = false;
prime[0] = false;
for (int p = 2; p * p <= MAX; p++) {
if (prime[p] == true) {
for (int i = p * 2; i <= MAX; i += p)
prime[i] = false;
}
}
}
void productOfKthPrimes(int arr[], int n, int k) {
int c = 0;
long long int product = 1;
for (int i = 0; i < n; i++) {
if (prime[arr[i]]) {
c++;
if (c % k == 0) {
product *= arr[i];
c = 0;
}
}
}
cout << product << endl;
}
int main() {
createsieve();
int n = 5, k = 2;
int arr[n] = {2, 3, 11, 13, 23};
productOfKthPrimes(arr, n, k);
return 0;
}
আউটপুট
39
