Common prime factors of two numbers
Given two integer and , the task is to find the common prime divisors of these numbers.
Examples:
Input: A = 6, B = 12
Output: 2 3
2 and 3 are the only common prime divisors of 6 and 12
Input: A = 4, B = 8
Output: 2
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 display the number.
Efficient Approach is to do following:
- Find Greatest Common Divisor (gcd) of the given numbers.
- Find prime factors of the GCD.
Efficient Approach for multiple queries: The above solution can be further optimized if there are multiple queries for common factors. The idea is based on Prime Factorization using Sieve O(log n) for multiple queries.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; #define MAXN 100001 bool prime[MAXN]; void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as 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 <= MAXN; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p as non-prime for ( int i = p * p; i <= MAXN; i += p) prime[i] = false ; } } } // Find the common prime divisors void common_prime( int a, int b) { // Get the GCD of the given numbers int gcd = __gcd(a, b); // Find the prime divisors of the gcd for ( int i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { cout << i << " " ; } } } // Driver code int main() { // Create the Sieve SieveOfEratosthenes(); int a = 6, b = 12; common_prime(a, b); return 0; } |
Java
//Java implementation of above approach class GFG { static final int MAXN = 100001 ; static boolean prime[] = new boolean [MAXN]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. for ( int i = 0 ;i<prime.length;i++) prime[i]= true ; // 0 and 1 are not prime numbers prime[ 0 ] = false ; prime[ 1 ] = false ; for ( int p = 2 ; p * p < MAXN; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p as non-prime for ( int i = p * p; i < MAXN; i += p) prime[i] = false ; } } } // Find the common prime divisors static void common_prime( int a, int b) { // Get the GCD of the given numbers int gcd = ( int ) __gcd(a, b); // Find the prime divisors of the gcd for ( int i = 2 ; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0 ) { System.out.print(i + " " ); } } } static long __gcd( long a, long b) { if (a == 0 ) return b; return __gcd(b % a, a); } // Driver code public static void main(String[] args) { // Create the Sieve SieveOfEratosthenes(); int a = 6 , b = 12 ; common_prime(a, b); } } /*This code is contributed by 29AjayKumar*/ |
Python3
# Python implementation of above approach from math import gcd, sqrt # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [ True ] * 100001 def SieveOfEratosthenes() : # 0 and 1 are not prime numbers prime[ 0 ] = False prime[ 1 ] = False for p in range ( 2 , int (sqrt( 100001 )) + 1 ) : # If prime[p] is not changed, # then it is a prime if prime[p] = = True : # Update all multiples of # p as non-prime for i in range (p * * 2 , 100001 , p) : prime[i] = False # Find the common prime divisors def common_prime(a, b) : # Get the GCD of the given numbers __gcd = gcd(a, b) # Find the prime divisors of the gcd for i in range ( 2 , __gcd + 1 ) : # If i is prime and a divisor of gcd if prime[i] and __gcd % i = = 0 : print (i, end = " " ) # Driver code if __name__ = = "__main__" : # Create the Sieve SieveOfEratosthenes() a, b = 6 , 12 common_prime(a, b) # This code is contributed by ANKITRAI1 |
C#
//C# implementation of above approach using System; public class GFG { static bool []prime = new bool [100001]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. for ( int i = 0;i<prime.Length;i++) prime[i]= true ; // 0 and 1 are not prime numbers prime[0] = false ; prime[1] = false ; for ( int p = 2; p * p < 100001; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p as non-prime for ( int i = p * p; i < 100001; i += p) prime[i] = false ; } } } // Find the common prime divisors static void common_prime( int a, int b) { // Get the GCD of the given numbers int gcd = ( int ) __gcd(a, b); // Find the prime divisors of the gcd for ( int i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { Console.Write(i + " " ); } } } static long __gcd( long a, long b) { if (a == 0) return b; return __gcd(b % a, a); } // Driver code public static void Main() { // Create the Sieve SieveOfEratosthenes(); int a = 6, b = 12; common_prime(a, b); } } /*This code is contributed by 29AjayKumar*/ |
Javascript
<script> // Javascript program to implement the above approach MAXN = parseInt(100001); prime = new Array(MAXN); function __gcd(a, b) { if (a == 0) return b; return __gcd(b % a, a); } function SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. prime.fill( true ); // 0 and 1 are not prime numbers prime[0] = false ; prime[1] = false ; for ( var p = 2; p * p <= MAXN; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p as non-prime for ( var i = p * p; i <= MAXN; i += p) prime[i] = false ; } } } // Find the common prime divisors function common_prime( a, b) { // Get the GCD of the given numbers var gcd = __gcd(a, b); // Find the prime divisors of the gcd for ( var i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { document.write( i + " " ); } } } SieveOfEratosthenes(); var a = 6, b = 12; common_prime(a, b); //This code is contributed by SoumikModnal </script> |
Output:
2 3
Contact Us