数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中计算两个数的共同质因数
假设我们有两个数字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的最大公约数 (GCD)。
创建一个从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
更新于：2020年5月15日
276 次浏览
广告