আমাদের দুটি সংখ্যা দেওয়া আছে, যেমন x এবং y, এবং আমাদের কাজ হল দুটি সংখ্যার সাধারণ প্রাইম ফ্যাক্টর খুঁজে বের করা। সাধারণ প্রাইম ফ্যাক্টর খুঁজে বের করতে প্রথমে দুটি সংখ্যার সাধারণ ফ্যাক্টরগুলো বের করতে হবে এবং তারপর সেই ফ্যাক্টর들 থেকে প্রাইম সংখ্যাগুলো বের করতে হবে।
উদাহরণ
ইনপুট − x = 10 y = 20 আউটপুট − সাধারণ প্রাইম ফ্যাক্টর: 2 5
ব্যাখ্যা − 10 এবং 20-এর সাধারণ প্রাইম ফ্যাক্টর শুধু 2 এবং 5।
ইনপুট − x = 34 y = 12 আউটপুট − সাধারণ প্রাইম ফ্যাক্টর: 2
ব্যাখ্যা − 34 এবং 12-এর সাধারণ প্রাইম ফ্যাক্টর শুধু 2।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- দুটি সংখ্যা
xএবংy-এর মান ইনপুট নিন - একটি ফাংশন তৈরি করুন এবং ফাংশনের ভিতরে
- একটি অস্থায়ী ভেরিয়েবল ঘোষণা করুন যা
xএবংy-এর গরিষ্ট সাধারণ ভাজক (GCD) ধারণ করবে i = 2থেকেi <= GCDপর্যন্ত লুপ তৈরি করুন- লুপের ভিতরে চেক করুন
prime[i] && GCD % i == 0এবং যদি সত্য হয় i-এর মান প্রিন্ট করুন- ফলাফল প্রিন্ট করুন
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
bool prime[MAX];
void SieveOfEratosthenes() {
// একটি বুলিয়ান অ্যারে "prime[0..n]" তৈরি করুন এবং সব এন্ট্রি true করুন
// prime[i] অবশেষে false হবে যদি i প্রাইম না হয়, অন্যথায় true
memset(prime, true, sizeof(prime));
// 0 এবং 1 প্রাইম নয়
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// যদি prime[p] পরিবর্তন না হয়, তবে এটি প্রাইম
if (prime[p] == true) {
// p-এর সব গুণককে non-prime হিসেবে আপডেট
for (int i = p * p; i <= MAX; i += p) {
prime[i] = false;
}
}
}
}
// সাধারণ প্রাইম সংখ্যা খুঁজে বের করার ফাংশন
void common_prime(int x, int y) {
// দেওয়া সংখ্যাগুলোর GCD বের করুন
int g = __gcd(x, y);
// g-এর প্রাইম ভাজক খুঁজুন
for (int i = 2; i <= (g); i++) {
// যদি i প্রাইম এবং g-এর ভাজক হয়
if (prime[i] && g % i == 0) {
cout << i << " ";
}
}
}
// main কোড
int main() {
// সিভ তৈরি
SieveOfEratosthenes();
int x = 20, y = 30;
cout << "Common prime factor of two numbers are: ";
common_prime(x, y);
return 0;
}
আউটপুট
যদি আমরা উপরের কোডটি রান করি তবে নিচের আউটপুট পাব −
Common prime factor of two numbers are: 2 5
