Generate K co-prime pairs of factors of a given number

0 0 4 minutes read

Given two integers N and K, the task is to find K pair of factors of the number N such that the GCD of each pair of factors is 1.
Note: K co-prime factors always exist for the given number
Examples:

Input: N = 6, K = 1
Output: 2 3
Explanation:
Since 2 and 3 are both factors of 6 and gcd(2, 3) = 1.
Input: N = 120, K = 4
Output:
2 3
3 4
3 5
4 5

Naive Approach:
The simplest approach would be to check all the numbers upto N and check if the GCD of the pair is 1.
Time Complexity: O(N²)
Space Complexity: O(1)
Linear Approach:
Find all possible divisors of N and store in another array. Traverse through the array to search for all possible coprime pairs from the array and print them.
Time Complexity: O(N)
Space Complexity: O(N)
Efficient Approach:
Follow the steps below to solve the problem:

It can be observed that if GCD of any number, say x, with 1 is always 1, i.e. GCD(1, x) = 1.
Since 1 will always be a factor of N, simply print any K factors of N with 1 as the coprime pairs.

Below is the implementation of the above approach.

C++

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function prints the
// required pairs
void FindPairs(int n, int k)
{
    // First co-prime pair
    cout << 1 << " " << n << endl;
 
    // As a pair (1 n) has
    // already been Printed
    k--;
 
    for (long long i = 2;
         i <= sqrt(n); i++) {
 
        // If i is a factor of N
        if (n % i == 0) {
 
            cout << 1 << " "
                 << i << endl;
            k--;
            if (k == 0)
                break;
 
            // Since (i, i) won't form
            // a coprime pair
            if (i != n / i) {
                cout << 1 << " "
                     << n / i << endl;
                k--;
            }
            if (k == 0)
                break;
        }
    }
}
 
// Driver Code
int main()
{
 
    int N = 100;
    int K = 5;
 
    FindPairs(N, K);
 
    return 0;
}

Java

// Java implementation of 
// the above approach 
import java.util.*;
 
class GFG{ 
 
// Function prints the 
// required pairs 
static void FindPairs(int n, int k) 
{ 
     
    // First co-prime pair 
    System.out.print(1 + " " + n + "\n"); 
 
    // As a pair (1 n) has 
    // already been Printed 
    k--; 
 
    for(long i = 2; i <= Math.sqrt(n); i++)
    { 
         
        // If i is a factor of N 
        if (n % i == 0)
        { 
            System.out.print(1 + " " + i + "\n"); 
            k--; 
            if (k == 0) 
                break; 
 
            // Since (i, i) won't form 
            // a coprime pair 
            if (i != n / i)
            { 
                System.out.print(1 + " " + 
                             n / i + "\n"); 
                k--; 
            } 
            if (k == 0) 
                break; 
        } 
    } 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
    int N = 100; 
    int K = 5; 
 
    FindPairs(N, K); 
}
} 
 
// This code is contributed by princiraj1992

Python3

# Python3 implementation of
# the above approach
from math import sqrt
 
# Function prints the
# required pairs
def FindPairs(n, k):
 
    # First co-prime pair
    print(1, n)
 
    # As a pair (1 n) has
    # already been Printed
    k -= 1
 
    for i in range(2, int(sqrt(n)) + 1):
 
        # If i is a factor of N
        if(n % i == 0):
            print(1, i)
 
            k -= 1
            if(k == 0):
                break
 
            # Since (i, i) won't form
            # a coprime pair
            if(i != n // i):
                print(1, n // i)
                k -= 1
 
            if(k == 0):
                break
 
# Driver Code
if __name__ == '__main__':
 
    N = 100
    K = 5
 
    FindPairs(N, K)
 
# This code is contributed by Shivam Singh

C#

// C# implementation of 
// the above approach 
using System;
 
class GFG{ 
 
// Function prints the 
// required pairs 
static void FindPairs(int n, int k) 
{ 
     
    // First co-prime pair 
    Console.Write(1 + " " + n + "\n"); 
 
    // As a pair (1 n) has 
    // already been Printed 
    k--; 
 
    for(long i = 2; i <= Math.Sqrt(n); i++)
    { 
         
        // If i is a factor of N 
        if (n % i == 0)
        { 
            Console.Write(1 + " " + i + "\n"); 
            k--; 
            if (k == 0) 
                break; 
 
            // Since (i, i) won't form 
            // a coprime pair 
            if (i != n / i)
            { 
                Console.Write(1 + " " + 
                          n / i + "\n"); 
                k--; 
            } 
            if (k == 0) 
                break; 
        } 
    } 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
    int N = 100; 
    int K = 5; 
 
    FindPairs(N, K); 
}
} 
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of
// the above approach
 
 
// Function prints the
// required pairs
function FindPairs(n, k)
{
    // First co-prime pair
    document.write(1 + " " + n + "<br>");
 
    // As a pair (1 n) has
    // already been Printed
    k--;
 
    for (let i = 2;
        i <= Math.sqrt(n); i++) {
 
        // If i is a factor of N
        if (n % i == 0) {
 
            document.write( 1 + " "
                + i + "<br>");
            k--;
            if (k == 0)
                break;
 
            // Since (i, i) won't form
            // a coprime pair
            if (i != n / i) {
                document.write(1 + " "
                    + n / i + "<br>");
                k--;
            }
            if (k == 0)
                break;
        }
    }
}
 
// Driver Code
 
let N = 100;
let K = 5;
 
FindPairs(N, K);
// This code is contributed by _saurabh_jaiswal
</script>

Output:

Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!