计算C ++中两个数字的公质数

  • Z时代
  • 2024-01-10
  • 分类：综合

我们给了两个数字，分别是x和y，任务是找到两个数字之间的公质因数。可以通过首先计算两个数字之间的公共数，然后从公共因子列表中检查一个是质数来找到公共质数。

例如

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

说明-10和20之间的公质数因子只有2和5。

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

说明-34和12之间的公质数是2。

以下程序中使用的方法如下

  • 输入两个数字x和y的值。

  • 创建一个函数并在函数内部

  • 声明一个临时变量，该变量将是数字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

以上是 计算C ++中两个数字的公质数 的全部内容， 来源链接： utcz.com/z/347406.html

回到顶部