Generar K pares coprimos de factores de un número dado

Dados dos enteros N y K , la tarea es encontrar K par de factores del número N tales que el MCD de cada par de factores sea 1. 
Nota: siempre existen K factores coprimos para el número dado
Ejemplos: 
 

Entrada: N = 6, K = 1 
Salida: 2 3 
Explicación: 
Dado que 2 y 3 son ambos factores de 6 y mcd(2, 3) = 1.
Entrada: N = 120, K = 4 
Salida: 
2 3 
3 4 
3 5 
4 5 
 

Enfoque ingenuo: 
el enfoque más simple sería verificar todos los números hasta N y verificar si el MCD del par es 1. 
Complejidad de tiempo: O(N ² ) 
Complejidad de espacio: O(1)
Enfoque lineal:  
encuentre todos los divisores posibles de N y almacenar en otra array. Recorra la array para buscar todos los pares coprimos posibles de la array e imprímalos. 
Complejidad de tiempo: O(N) 
Complejidad de espacio: O(N)
Enfoque eficiente: 
Siga los pasos a continuación para resolver el problema:

• Se puede observar que si MCD de cualquier número, digamos x , con 1 es siempre 1, es decir, MCD(1, x) = 1 .
• Dado que 1 siempre será un factor de N , simplemente imprima cualquier K factores de N con 1 como pares coprimos .

A continuación se muestra la implementación del enfoque anterior.
 

// 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 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 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# 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

<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>

1 100
1 2
1 50
1 4
1 25

Complejidad de tiempo: O(sqrt(N)) 
Espacio auxiliar: O(1)