हमें दो नंबर दिए गए हैं मान लीजिए x और y और कार्य दो संख्याओं के बीच सामान्य अभाज्य गुणनखंडों को खोजना है। सामान्य अभाज्य गुणनखंडों को पहले दो संख्याओं के बीच की सामान्य संख्याओं की गणना करके और उसके बाद सामान्य कारकों की सूची से जाँच करके पाया जा सकता है कि जो अभाज्य संख्याएँ हैं।
उदाहरण के लिए
Input − x = 10 y = 20 Output − Common prime factor of two numbers are: 2 5
स्पष्टीकरण − 10 और 20 के बीच सामान्य अभाज्य गुणनखंड केवल 2 और 5 हैं।
Input − x = 34 y = 12 Output − Common prime factor of two numbers are: 2
स्पष्टीकरण −34 और 12 के बीच सामान्य अभाज्य गुणनखंड 2 हैं।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
दो संख्याओं x और y के मान दर्ज करें।
-
एक फंक्शन बनाएं और एक फंक्शन के अंदर
-
एक अस्थायी चर घोषित करें जो संख्याओं x और y का सबसे बड़ा सामान्य भाजक होगा
-
2 से शुरू होकर GCD से कम या उसके बराबर होने तक एक लूप बनाएं और i को बढ़ाएँ
-
लूप के अंदर जांचें कि क्या prime[i] &&GCD%i =0 और अगर यह सच है
-
i
. का मान प्रिंट करें -
परिणाम प्रिंट करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
bool prime[MAX];
void SieveOfEratosthenes(){
// Create a boolean array "prime[0..n]" and initialize
// all entries are 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[0] = false;
prime[1] = false;
for (int p = 2; p * p <= MAX; p++){
// If prime[p] is not changed, then it is a prime
if (prime[p] == true){
// Updating all multiples of p as non-prime
for (int i = p * p; i <= MAX; i += p){
prime[i] = false;
}
}
}
}
// Function to find the common prime numbers
void common_prime(int x, int y){
// Obtain the GCD of the given numbers
int g = __gcd(x, y);
// Find the prime divisors of the g
for (int i = 2; i <= (g); i++){
// If i is prime and divisor of g
if (prime[i] && g % i == 0){
cout << i << " ";
}
}
}
// main code
int main(){
// Creating the Sieve
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