Print all unitary divisors of a natural number

Updated

Given a natural number n, print all Unitary divisors of it.

A natural number i is an unitary divisor (or Hall divisor) of a number n if i is a divisor of n and if i and \(\frac {n}{i}\) are coprime.

Examples :

Input : n = 12
Output : 1 3 4 12
 2 and 12/2 are not coprime
 so they are not printed

Input : n = 100
Output : 1 4 25 100

Approach :

All the divisors are present in pairs. For example if n = 100, then the various pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10).Using this fact we could speed up our program significantly. We, however have to careful if there are two equal divisors as in case of (10, 10). In such case we’d print only one of them. But before printing unitary divisor i we will also check if i and \(\frac {n}{i}\) are coprime that is their GCD is 1, then only we will print the pair.

Implementation :

// Program to find all unitary divisiors
// of a number
#include <bits/stdc++.h>
using namespace std;
// Function to print the unitary divisors
void printUnitaryDivisors(int n)
{
    // Note that this loop runs till square root
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i && __gcd(i, n/i) == 1)
            {
                printf("%d ", i);
            }

            else // Otherwise print both
            {
                if(__gcd(i, n/i) == 1)
                printf("%d %d ", i, n/i);
            }
        }
    }
}

/* Driver program to test above function */
int main()
{
    printf("The Unitary divisors of 12 are: \n");
    printUnitaryDivisors(12);
    return 0;
}

Output :

The Unitary divisors of 12 are: 
1 12 3 4

Time Complexity : O(sqrt(n)) Auxiliary Space : O(1)

Comment
Mithlesh Upadhyay Published 21 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials