计算C ++中两个数字的公质数
我们给了两个数字，分别是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