Divisores coprimos de un número

Dado un número entero N . La tarea es encontrar un par de divisores coprimos de N mayores que 1. Si tales divisores no existen, imprima ‘-1’. 

Ejemplos:

Entrada: N = 45 
Salida: 3 5 
Explicación: Como 3 y 5 son divisores de 45 y mcd( 3, 5 ) = 1 . 
Por lo tanto, cumplen la condición.

Entrada: N = 25 
Salida: -1 
Explicación: Ningún par de divisores de 25 satisface la condición tal 
que su mcd sea 1.

Acercarse: 

1. Iterar de x = 2 a sqrt(N), para encontrar todos los divisores de N
2. Para cualquier valor de x, comprueba si divide a N
3. Si divide, sigue dividiendo N por x mientras sea divisible.
4. Ahora, comprueba si N > 1, entonces el par de divisores (x, N) tendrá 
   mcd(x, N) == 1, ya que todos los factores de ‘x’ han sido eliminados de N.
5. Del mismo modo, verifique todos los valores de x.

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

// C++ program to find two coprime
// divisors of a given number
// such that both are greater
// than 1
 
#include <bits/stdc++.h>
using namespace std;
 
// Function which finds the
// required pair of divisors
// of N
void findCoprimePair(int N)
{
    // We iterate upto sqrt(N)
    // as we can find all the
    // divisors of N in this
    // time
    for (int x = 2; x <= sqrt(N); x++) {
        if (N % x == 0) {
            // If x is a divisor of N
            // keep dividing as long
            // as possible
            while (N % x == 0) {
                N /= x;
            }
            if (N > 1) {
                // We have found a
                // required pair
                cout << x << " "
                     << N << endl;
                return;
            }
        }
    }
    // No such pair of divisors
    // of N was found, hence
    // print -1
    cout << -1 << endl;
}
 
// Driver Code
int main()
{
    // Sample example 1
    int N = 45;
    findCoprimePair(N);
 
    // Sample example 2
    N = 25;
    findCoprimePair(N);
    return 0;
}

// Java program to find two coprime
// divisors of a given number
// such that both are greater
// than 1
import java.util.*;
 
class GFG{
     
// Function which finds the
// required pair of divisors
// of N
public static void findCoprimePair(int N)
{
     
    // We iterate upto sqrt(N)
    // as we can find all the
    // divisors of N in this
    // time
    for(int x = 2; x <= Math.sqrt(N); x++)
    {
        if (N % x == 0)
        {
             
            // If x is a divisor of N
            // keep dividing as long
            // as possible
            while (N % x == 0)
            {
                N /= x;
            }
            if (N > 1)
            {
                 
                // We have found a
                // required pair
                System.out.println(x + " " + N);
                return;
            }
        }
    }
     
    // No such pair of divisors
    // of N was found, hence
    // print -1
    System.out.println(-1);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Sample example 1
    int N = 45;
    findCoprimePair(N);
   
    // Sample example 2
    N = 25;
    findCoprimePair(N);
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to find two coprime
# divisors of a given number such that
# both are greater than 1
import math
 
# Function which finds the
# required pair of divisors
# of N
def findCoprimePair(N):
     
    # We iterate upto sqrt(N)
    # as we can find all the
    # divisors of N in this
    # time
    for x in range(2, int(math.sqrt(N)) + 1):
        if (N % x == 0):
             
            # If x is a divisor of N
            # keep dividing as long
            # as possible
            while (N % x == 0):
                N //= x
 
            if (N > 1):
 
                # We have found a
                # required pair
                print(x, N)
                return;
 
    # No such pair of divisors
    # of N was found, hence
    # print -1
    print("-1")
 
# Driver Code
 
# Sample example 1
N = 45
findCoprimePair(N)
 
# Sample example 2
N = 25
findCoprimePair(N)
 
# This code is contributed by Vishal Maurya.

// C# program to find two coprime
// divisors of a given number
// such that both are greater
// than 1
using System;
class GFG{
     
// Function which finds the
// required pair of divisors
// of N
public static void findCoprimePair(int N)
{
  // We iterate upto sqrt(N)
  // as we can find all the
  // divisors of N in this
  // time
  for(int x = 2;
          x <= Math.Sqrt(N); x++)
  {
    if (N % x == 0)
    {
      // If x is a divisor of N
      // keep dividing as long
      // as possible
      while (N % x == 0)
      {
        N /= x;
      }
      if (N > 1)
      {
        // We have found a
        // required pair
        Console.WriteLine(x +
                          " " + N);
        return;
      }
    }
  }
 
  // No such pair of divisors
  // of N was found, hence
  // print -1
  Console.WriteLine(-1);
}
 
// Driver code
public static void Main(String[] args)
{   
  // Sample example 1
  int N = 45;
  findCoprimePair(N);
 
  // Sample example 2
  N = 25;
  findCoprimePair(N);
}
}
 
// This code is contributed by Chitranayal

<script>
 
// JavaScript program to find two coprime
// divisors of a given number
// such that both are greater
// than 1
 
// Function which finds the
// required pair of divisors
// of N
function findCoprimePair(N)
{
    // We iterate upto sqrt(N)
    // as we can find all the
    // divisors of N in this
    // time
    for (let x = 2; x <= Math.sqrt(N); x++) {
        if (N % x == 0) {
            // If x is a divisor of N
            // keep dividing as long
            // as possible
            while (N % x == 0) {
                N = Math.floor(N / x);
            }
            if (N > 1) {
                // We have found a
                // required pair
                document.write(x + " "
                    + N + "<br>");
                return;
            }
        }
    }
    // No such pair of divisors
    // of N was found, hence
    // print -1
    document.write(-1 + "<br>");
}
 
// Driver Code
    // Sample example 1
    let N = 45;
    findCoprimePair(N);
 
    // Sample example 2
    N = 25;
    findCoprimePair(N);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

3 5
-1

Complejidad de tiempo : O( sqrt(N) )