# Print all numbers that are divisors of N and are co-prime with the quotient of their division

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 12Output:1 3 4 12Explanation:

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 = 100Output: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 division` `void` `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 Code` `int` `main()` `{` ` ` `int` `N = 12;` ` ` `printUnitaryDivisors(N);` ` ` `return` `0;` `}` |

## Python3

`# python 3 program for the above approach` `from` `math ` `import` `sqrt, gcd` `# Function to print all numbers` `# that are divisors of N and are` `# co-prime with the quotient` `# of their division` `def` `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 Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `12` ` ` `printUnitaryDivisors(N)` ` ` `# This code is contributed by ipg2016107.` |

## C#

`// C# program for the above approach` `using` `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 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) {` ` ` `Console.Write(i+` `" "` `);` ` ` `}` ` ` `// Otherwise print both` ` ` `else` `{` ` ` `if` `(gcd(i, n / i) == 1) {` ` ` `Console.Write(i + ` `" "` `+n / i+ ` `" "` `);` ` ` `}` ` ` `}` ` ` `}` ` ` `}` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 12;` ` ` `printUnitaryDivisors(N);` `}` `}` `// This code is contributed by SURENDRA_GANGWAR.` |

## Java

`// Java program for tha above approach` `import` `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 tha above approach` `function` `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>` |

**Output:**

1 12 3 4

**Time Complexity:** O(√N*log N)**Auxiliary Space:** O(1)