C++で2つの数の一般的な素因数を数える

xとyの2つの数が与えられ、タスクは2つの数の間の共通の素因数を見つけることです。共通の素因数は、最初に2つの数の間の共通の数を計算し、その後、共通の因子のリストから素数であるものをチェックすることによって見つけることができます。

例

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の2つの数値を入力します。

• 関数を作成し、関数内に

• 数xとyの最大公約数となる一時変数を宣言します

• 2からGCD以下になるまでループを作成し、iをインクリメントします

• ループ内で、prime [i] &&GCD％i =0であるかどうか、およびこれがtrueであるかどうかを確認します

• 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