একটি অ্যারে arr[n] দেওয়া আছে। এর মধ্যে থাকা সব কম্পোজিট নম্বরের গুণফল বের করতে হবে।
কম্পোজিট নম্বর হলো যেসব পূর্ণসংখ্যা দুইটি অন্য পূর্ণসংখ্যা গুণ করে তৈরি হয় (যেমন ৬ = ২×৩)। এগুলো প্রাইম নয়।
ইনপুট − arr[] = {1,2,4,5,6,7}
আউটপুট − 24
ব্যাখ্যা − কম্পোজিট নম্বর: ৪, ৬। গুণফল = ২৪।
ইনপুট − arr[] = {10,2,4,5,6,11}
আউটপুট − 240
ব্যাখ্যা − কম্পোজিট নম্বর: ১০, ৪, ৬। গুণফল = ২৪০।
প্রোগ্রামে ব্যবহৃত পদ্ধতি (Sieve)
- অ্যারের সর্বোচ্চ ভ্যালু বের করুন।
- সিভ অফ এরাটোস্থেনিস দিয়ে প্রাইম নম্বর চিহ্নিত করুন।
- অ্যারে ট্রাভার্স করে যেসব প্রাইম নয় (কম্পোজিট), তাদের গুণফল বের করুন।
অ্যালগরিদম
Start
function product_arr(arr, size)
max = max_element(arr)
prime[max+1] = all true
prime[0]=prime[1]=true // 0,1 প্রাইম নয়
for i=2 to sqrt(max)
if prime[i]
for j=i*2 to max step i: prime[j]=false
product = 1
for i=0 to size-1
if !prime[arr[i]]: product *= arr[i]
return product
Stop
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int product_arr(int arr[], int size) {
int max = *max_element(arr, arr + size);
vector prime(max + 1, true);
prime[0] = prime[1] = true; // 0,1 প্রাইম নয়
for (int i = 2; i * i <= max; i++) {
if (prime[i]) {
for (int j = i * 2; j <= max; j += i)
prime[j] = false;
}
}
int product = 1;
for (int i = 0; i < size; i++)
if (!prime[arr[i]])
product *= arr[i];
return product;
}
int main() {
int arr[] = {2, 4, 6, 8, 10};
int size = sizeof(arr)/sizeof(arr[0]);
cout << "product of composite numbers in array: " << product_arr(arr, size);
return 0;
} আউটপুট
product of composite numbers in array: 1920
