Đếm các thừa số nguyên tố chung của hai số trong C ++

Chúng ta được cung cấp hai số, giả sử x và y và nhiệm vụ là tìm các thừa số nguyên tố chung giữa hai số. Thừa số nguyên tố chung có thể được tìm thấy trước tiên bằng cách tính các số chung giữa hai số và sau đó kiểm tra từ danh sách các thừa số chung để tìm ra các số nguyên tố.

Ví dụ

Input − x = 10 y = 20
Output − Common prime factor of two numbers are: 2 5

Giải thích - các thừa số nguyên tố chung từ 10 đến 20 chỉ là 2 và 5.

Input − x = 34 y = 12
Output − Common prime factor of two numbers are: 2

Giải thích - các thừa số nguyên tố chung từ 34 đến 12 là 2.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nhập giá trị của hai số x và y.

• Tạo một hàm và bên trong một hàm

• Khai báo một biến tạm thời sẽ là ước số chung lớn nhất của các số x và y

• Tạo một vòng lặp bắt đầu từ số 2 cho đến khi nó nhỏ hơn hoặc bằng GCD và tăng i

• Bên trong vòng lặp, hãy kiểm tra xem số nguyên tố [i] &&GCD% i =0 và điều này có đúng không

• In giá trị của i

• In kết quả

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Common prime factor of two numbers are: 2 5