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)