# All Divisors of a number

Sun Feb 06 2022 05:06:01 GMT+0000 (UTC)

```// Efficient Code with Sorted Order

static void printDivisors(int n)
{
int i = 1;
// Print all divisors from 1(inlcusive) to sqrt(n) (exclusive)
for(i=1; i*i < n; i++)
{
if(n % i == 0)
{
System.out.print(i+" ");
}
}
// Print all divisors from sqrt(n)(inlcusive) to n (inclusive)
for(; i >= 1; i--)
{
if(n % i == 0)
{
System.out.print((n / i)+" ");
}
}
}

//Efficient Code : Time Complexity: O(sqrt(n)) , Auxiliary Space : O(1)

static void printDivisors(int n)
{
for(int i=1; i*i <= n; i++)
{
if(n % i == 0)
{
System.out.print(i+" ");

if(i != n / i)
System.out.print((n / i)+" ");
}
}
}

// Naive Solution : Time Complexity : O(n) , Auxiliary Space : O(1)

static void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
System.out.print(i+" ");
}```
content_copyCOPY

Find all factors of a natural number Given a natural number n, print all distinct divisors of it. Examples: Input : n = 10 Output: 1 2 5 10 Input: n = 100 Output: 1 2 4 5 10 20 25 50 100 Input: n = 125 Output: 1 5 25 125 Naive solution: ----------------- A Naive Solution would be to iterate all the numbers from 1 to n, checking if that number divides n and printing it. Efficient Solution: ------------------- 1.) Divisors always appear in pairs 30 : (1,30) , (2,15) , (3,10) , (5,6) 2.) One of the divisors in every pair is smaller than or equal to sqrt(n) For a pair (x,y) x * y = n Let x be the smaller, i.e; x <= y If x<=y x * x <= n x <= sqrt(n)