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(N2)
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 pairsvoid 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 Codeint 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 approachfrom math import sqrt# Function prints the# required pairsdef 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 Codeif __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 pairsfunction 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 Codelet N = 100;let K = 5;FindPairs(N, K);// This code is contributed by _saurabh_jaiswal</script> |
Output:
1 100 1 2 1 50 1 4 1 25
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!
