Common Prime Factors of a Two Number using C++

Suppose we are given two integers, our task is to find the common prime factors of those two numbers.

A basic method two achieve this comprises of two steps. Firstly, by finding the common factors between the two given numbers and then, checking each of these common factors for which of them are prime using C++ program.

An effective and optimized approach would be to:

• First, find the Greatest Common Divisor(GCD) of the two numbers.
• Then, we find the prime factors of the GCD of the two numbers.

We have to take two integer inputs from the user and then print the output for them.

For example:

• Input: 10, 20

         Output: 2, 5

• Input: 34, 12

         Output: 2

• Input: 6, 12  

         Output: 2, 3

Algorithm for finding the Common Prime Factors of two numbers

1. Take input of two numbers, m and n, from the user.
2. Make a function, Sieve_Of_Eratosthenes(), which would create a boolean array and initializing all it’s values as “true”.
3. After this, we will change all composite prime[i] values to “false”, using a loop.
4. Create another function and in that, store the Greatest Common Divisor(GCD) of the two numbers in a temporary variable.
5. Inside the same function start a loop from 2 till less than or equal to GCD.
6. Inside the loop put an if condition to check if prime[i] && GCD%i = 0 and if this is true then print that i.
7. All the values of i that have been printed are the Common Prime Factors of the two numbers.

C++ code to find the Common Prime Factors of two numbers

#include<bits/stdc++.h>
using namespace std;

#define MAX_SIZE 1000
bool prime[MAX_SIZE];

void Sieve_Of_Eratosthenes()
{
  //creating a boolean array and initializing all values as "true"
  memset(prime, true, sizeof(prime));

  //now we will change all composite prime[i] values to "false"
  //as 0 and 1 are not primes
  prime[0]=false;
  prime[1]=false;

  //loop for the rest of the values
  for(int j=2 ; j*j<=MAX_SIZE ; j++)
    {
    if(prime[j] == true)
        {
      //changing the values of all composites to "false"
      for(int i= j*j ; i<=MAX_SIZE ; i += j)
                prime[i]=false;
    }
  }
}

//function to find the common prime factors
void Common_Prime_Factors(int m, int n)
{
    //variables used
    int i, GCD;

  //using library function to get GCD of two numbers
  GCD = __gcd(m, n);

  //loop to find prime factors of GCD
  for(i=2 ; i<=GCD ; i++)
    {

    // If i is prime and a divisor of gcd
    if(prime[i] && GCD%i == 0)
        {
      cout<<i<<endl;
    }
  }
}

//int main/driver code
int main()
{
    //variables used
    int m, n;

    //Taking the input from the user
    cout<<"Enter two numbers to find their common prime factors: ";
    cin>>m>>n;

  //calling function to create the Sieve of Eratosthenes
  Sieve_Of_Eratosthenes();

  cout<<"\nThe common prime  factors of "<<m<<" and "<<n<<" are:"<<endl;

  //calling the function to find the common prime factors
  Common_Prime_Factors(m, n);

  return 0;
}

Output

Enter two numbers to find their common prime factors: 22
44

The common prime  factors of 22 and 44 are:
2
11

Note

• This solution only takes in account only two numbers. We can expand the code to calculate the common prime factors for more numbers as well.
• An optimised approach for the same would be to use the idea of Prime Factorization using Sieve, for multiple inputs. 
• In case of no Common Prime Factors of the two numbers, we can also add an cout statement for the same. This case is not included right now.

Some related topics which might be helpful are:

• Find Prime Numbers in a Range in C++ (Segmented Sieve Method)
• Sieve of Eratosthenes in C++
• Check if a given number is Prime or Composite in C++