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 Nvoid 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 Codeint 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 codepublic 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 1N = 45findCoprimePair(N)# Sample example 2N = 25findCoprimePair(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 codepublic 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 Nfunction 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
