Count common prime factors of two numbers
Given two integer and , the task is to find the count of common factors of two numbers where factors are prime.
Examples:
Input: A = 6, B = 12
Output: 2
2 and 3 are the only common prime divisors of 6 and 12
Input: A = 4, B = 8
Output: 1
Naive Approach: Iterate from 1 to min(A, B) and check whether i is prime and a factor of both A and B, if yes then increment the counter.
Efficient Approach is to do following:
- Find Greatest Common Divisor (gcd) of the given numbers.
- Find prime factors of the GCD.
Below is the implementation of the above approach:
C++
// CPP program to count common prime factors // of a and b. #include <bits/stdc++.h> using namespace std; // A function to count all prime factors of // a given number x int countPrimeFactors( int x) { int res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i <= sqrt (x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res; } // Count of common prime factors int countCommonPrimeFactors( int a, int b) { // Get the GCD of the given numbers int gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd); } // Driver code int main() { int a = 6, b = 12; cout << countCommonPrimeFactors(a, b); return 0; } |
C
// C program to count common prime factors // of a and b. #include <stdio.h> #include <math.h> // A function to count all prime factors of // a given number x int countPrimeFactors( int x) { int res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i <= sqrt (x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res; } // Count of common prime factors int countCommonPrimeFactors( int a, int b) { int gcd, i; // Get the GCD of the given numbers for (i = 1; i <= a && i <= b; ++i) { // Checks if i is factor of both integers if (a % i == 0 && b % i == 0) gcd = i; } // Count prime factors in GCD return countPrimeFactors(gcd); } // Driver code int main() { int a = 6, b = 12; printf ( "%d" ,countCommonPrimeFactors(a, b)); return 0; } // This code is contributed by kothavvsaakash. |
Java
// Java program to count common prime factors // of a and b. import java.io.*; class GFG { // Recursive function to return gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 ) return b; if (b == 0 ) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // A function to count all prime factors of // a given number x static int countPrimeFactors( int x) { int res = 0 ; if (x % 2 == 0 ) { res++; // Print the number of 2s that divide x while (x % 2 == 0 ) x = x / 2 ; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3 ; i <= Math.sqrt(x); i = i + 2 ) { if (x % i == 0 ) { // While i divides x, print i and // divide x res++; while (x % i == 0 ) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2 ) res++; return res; } // Count of common prime factors static int countCommonPrimeFactors( int a, int b) { // Get the GCD of the given numbers int gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd); } // Driver code public static void main (String[] args) { int a = 6 , b = 12 ; System.out.println(countCommonPrimeFactors(a, b)); } } // This code is contributed by inder_verma.. |
Python3
# Python 3 program to count common prime # factors of a and b. from math import sqrt,gcd # A function to count all prime # factors of a given number x def countPrimeFactors(x): res = 0 if (x % 2 = = 0 ): res + = 1 # Print the number of 2s that divide x while (x % 2 = = 0 ): x = x / 2 # x must be odd at this point. So we # can skip one element (Note i = i +2) k = int (sqrt(x)) + 1 for i in range ( 3 , k, 2 ): if (x % i = = 0 ): # While i divides x, print i # and divide x res + = 1 while (x % i = = 0 ): x = x / i # This condition is to handle the # case when x is a prime number # greater than 2 if (x > 2 ): res + = 1 return res # Count of common prime factors def countCommonPrimeFactors(a, b): # Get the GCD of the given numbers gcd__ = gcd(a, b) # Count prime factors in GCD return countPrimeFactors(gcd__) # Driver code if __name__ = = '__main__' : a = 6 b = 12 print (countCommonPrimeFactors(a, b)) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to count common prime factors // of a and b. using System ; class GFG { // Recursive function to return gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // A function to count all prime factors of // a given number x static int countPrimeFactors( int x) { int res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i <= Math.Sqrt(x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res; } // Count of common prime factors static int countCommonPrimeFactors( int a, int b) { // Get the GCD of the given numbers int gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd); } // Driver code public static void Main() { int a = 6, b = 12; Console.WriteLine(countCommonPrimeFactors(a, b)); } // This code is contributed by Ryuga } |
PHP
<?php // PHP program to count common // prime factors of a and b. // Recursive function to return // gcd of a and b function __gcd( $a , $b ) { // Everything divides 0 if ( $a == 0) return $b ; if ( $b == 0) return $a ; // base case if ( $a == $b ) return $a ; // a is greater if ( $a > $b ) return __gcd(( $a - $b ), $b ); return __gcd( $a , ( $b - $a )); } // A function to count all prime // factors of a given number x function countPrimeFactors( $x ) { $res = 0; if ( $x % 2 == 0) { $res ++; // Print the number of 2s that // divide x while ( $x % 2 == 0) $x = $x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( $i = 3; $i <= sqrt( $x ); $i = $i + 2) { if ( $x % $i == 0) { // While i divides x, print i // and divide x $res ++; while ( $x % $i == 0) $x = $x / $i ; } } // This condition is to handle the case // when x is a prime number greater than 2 if ( $x > 2) $res ++; return $res ; } // Count of common prime factors function countCommonPrimeFactors( $a , $b ) { // Get the GCD of the given numbers $gcd = __gcd( $a , $b ); // Count prime factors in GCD return countPrimeFactors( $gcd ); } // Driver code $a = 6; $b = 12; echo (countCommonPrimeFactors( $a , $b )); // This code is contributed by akt_mit.. ?> |
Javascript
<script> // Javascript program to count // common prime factors of a and b. // Recursive function to return // gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // A function to count all prime factors of // a given number x function countPrimeFactors(x) { let res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = parseInt(x / 2, 10); } // x must be odd at this point. So we // can skip one element (Note i = i +2) for (let i = 3; i <= Math.sqrt(x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = parseInt(x / i, 10); } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res; } // Count of common prime factors function countCommonPrimeFactors(a, b) { // Get the GCD of the given numbers let gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd); } let a = 6, b = 12; document.write(countCommonPrimeFactors(a, b)); </script> |
Output:
2
Time Complexity: O(sqrtn*logn)
Auxiliary Space: O(1)
If there are multiple queries for counting common divisors, we can further optimize above code using Prime Factorization using Sieve O(log n) for multiple queries
Contact Us