เราได้รับตัวเลขสองตัว สมมติว่า 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
-
สร้างลูปตั้งแต่ 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
