Coprime divisors of a number

0 0 4 minutes read

Given an integer N. The task is to find a pair of co-prime divisors of N, greater than 1. If such divisors don’t exists then print ‘-1’.

Examples:

Input: N = 45
Output: 3 5
Explanation: Since 3 and 5 are divisors of 45 and gcd( 3, 5 ) = 1 .
Hence, they satisfy the condition.

Input: N = 25
Output: -1
Explanation: No pair of divisors of 25 satisfy the condition such
that their gcd is 1.

Approach:

Iterate from x = 2 to sqrt(N), to find all divisors of N
For any value x, check if it divides N
If it divides, then keep dividing N by x as long as it is divisible.
Now, check if N > 1, then the pair of divisors (x, N) will have
gcd(x, N) == 1, since all the factors of ‘x’ has been eliminated from N.
Similarly, check for all values of x.

Below is the implementation of the above approach:

C++

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

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

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

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

Javascript

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

Output:

3 5
-1

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!