Given a positive integer N, the task is to print all the numbers, say K, such that K is a divisor of N and K and N / K are coprime.
Examples:
Input: N = 12
Output: 1 3 4 12
Explanation:
All numbers K such that it is divisor of N(= 12) and K and N/K are coprime:
- 1: Since 1 is a divisor of 12 and 1 and 12(= 12/1) are coprime.
- 3: Since 3 is a divisor of 12 and 3 and 4( = 12/3) are coprime.
- 4: Since 4 is a divisor of 12 and 4 and 3( = 12/4) are coprime.
- 12: Since 12 is a divisor of 12 and 12 and 1( = 12/12) are coprime.
Input: N = 100
Output: 1 4 25 100
Naive Approach: The simplest approach to solve the given problem is to iterate over the range [1, N] and check for each number K whether K is a divisor of N and GCD of K and N/K is 1 or not. If found to be true, then print K. Otherwise, check for the next number.
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using the observation that all the divisors are present in pairs. For Example, if N is 100, then all the pairs of divisors are: (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).
Therefore, the idea is to iterate in the range [1, ?N] and check if both the given conditions are satisfied or not i.e., whether any number K is a divisor of N and GCD of K and N/K is 1 or not. If found to be true, then print both the numbers. In the case of two equal divisors, print only one of them.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print all numbers// that are divisors of N and are// co-prime with the quotient// of their divisionvoid printUnitaryDivisors(int n){ // Iterate upto square root of N for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && __gcd(i, n / i) == 1) { printf("%d ", i); } // Otherwise print both else { if (__gcd(i, n / i) == 1) { printf("%d %d ", i, n / i); } } } }}// Driver Codeint main(){ int N = 12; printUnitaryDivisors(N); return 0;} |
Python3
# python 3 program for the above approachfrom math import sqrt, gcd# Function to print all numbers# that are divisors of N and are# co-prime with the quotient# of their divisiondef printUnitaryDivisors(n): # Iterate upto square root of N for i in range(1,int(sqrt(n)) + 1, 1): if (n % i == 0): # If divisors are equal and gcd is # 1, then print only one of them if (n // i == i and gcd(i, n // i) == 1): print(i) # Otherwise print both else: if (gcd(i, n // i) == 1): print(i, n // i,end = " ") # Driver Codeif __name__ == '__main__': N = 12 printUnitaryDivisors(N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b);}// Function to print all numbers// that are divisors of N and are// co-prime with the quotient// of their divisionstatic void printUnitaryDivisors(int n){ // Iterate upto square root of N for (int i = 1; i <= (int)Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && gcd(i, n / i) == 1) { Console.Write(i+" "); } // Otherwise print both else { if (gcd(i, n / i) == 1) { Console.Write(i + " " +n / i+ " "); } } } }}// Driver Codepublic static void Main(){ int N = 12; printUnitaryDivisors(N);}}// This code is contributed by SURENDRA_GANGWAR. |
Java
// Java program for the above approachimport java.util.*;class GFG { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Function to print all numbers // that are divisors of N and are // co-prime with the quotient // of their division static void printUnitaryDivisors(int n) { // Iterate upto square root of N for (int i = 1; i <= (int)Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && gcd(i, n / i) == 1) { System.out.print(i + " "); } // Otherwise print both else { if (gcd(i, n / i) == 1) { System.out.print(i + " " + n / i + " "); } } } } } // Driver Code public static void main(String[] args) { int N = 12; printUnitaryDivisors(N); }} |
Javascript
<script>// JavaScript program for the above approachfunction gcd( a, b) { return b == 0 ? a : gcd(b, a % b); } // Function to print all numbers // that are divisors of N and are // co-prime with the quotient // of their division function printUnitaryDivisors( n) { // Iterate upto square root of N for (var i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && gcd(i, n / i) == 1) { document.write(i + " "); } // Otherwise print both else { if (gcd(i, n / i) == 1) { document.write(i + " " + n / i + " "); } } } } } // Driver Code var N = 12; printUnitaryDivisors(N); // This code is contributed by shivanisingh2110 </script> |
1 12 3 4
Time Complexity: O(?N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
