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
를 증가시킵니다. -
루프 내에서 프라임[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