資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告