All Divisors of Number

Given a positive integer n, your task is to find all of its divisors.

A divisor of a number n is any number that divides n completely (i.e., leaves no remainder).

Return the list of all such numbers in ascending order.

Understanding the Problem

We are given a positive integer n, and we need to find all of its divisors.

A divisor is any number that divides n exactly, meaning the remainder is zero.

For example, if n = 12, the numbers 1, 2, 3, 4, 6, 12 are all divisors because they divide 12 without leaving a remainder.

Our goal is to return all such numbers in ascending order.

Step-by-Step Solution with Example

Step 1: Initialize an empty list

We start by creating an empty list to collect the divisors.

Step 2: Loop from 1 to √n

Why √n? Because if i is a divisor of n, then n / i is also a divisor.

For example, for n = 12:

• 1 divides 12 → pair is (1, 12)
• 2 divides 12 → pair is (2, 6)
• 3 divides 12 → pair is (3, 4)

After i = 3, any new i would result in a repeated or reversed pair.

Step 3: Check if i divides n

Inside the loop, check if n % i == 0.

If it does, add i to the list.

Also, add n / i as long as it is different from i (to avoid adding square roots twice).

Step 4: Sort the list

Since we are adding pairs in no particular order, sort the final list of divisors before returning.

Let’s go through an example: n = 12

Initialize divisors = []

Loop i from 1 to √12 (which is about 3.46, so go up to 3)

• i = 1 → 12 % 1 == 0 → add 1 and 12
• i = 2 → 12 % 2 == 0 → add 2 and 6
• i = 3 → 12 % 3 == 0 → add 3 and 4

Now we have: [1, 12, 2, 6, 3, 4]

After sorting: [1, 2, 3, 4, 6, 12]

Edge Cases

• n = 1: The only divisor is 1.
• n is a prime number (e.g., 7): The divisors will be only 1 and n itself.
• n is a perfect square (e.g., 36): Be careful not to add the square root twice. For example, 6 * 6 = 36, so we only add 6 once.

Final Thoughts

This method is efficient because we reduce the number of iterations from n to about √n.

It works for all positive integers and ensures correct results even when n is very large.

Sorting at the end guarantees the result is in ascending order, as required.

This approach is both beginner-friendly and optimal for number theory-related problems in competitive programming.

1. Initialize an empty list to store divisors.
2. Iterate from 1 to sqrt(n).
3. If i divides n (i.e., n % i == 0):
• Add i to the list.
• If i != n/i, also add n/i to the list.
4. Sort the list of divisors before returning.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int cmpfunc(const void* a, const void* b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x - y);
}

int main() {
    int n = 36;  // Example number
    int maxDivisors = 1000;
    int divisors[maxDivisors];
    int count = 0;
    int sqrtN = (int)sqrt(n);

    for (int i = 1; i <= sqrtN; i++) {
        if (n % i == 0) {
            divisors[count++] = i;
            if (i != n / i) {
                divisors[count++] = n / i;
            }
        }
    }

    qsort(divisors, count, sizeof(int), cmpfunc);

    printf("Divisors of %d: ", n);
    for (int i = 0; i < count; i++) {
        printf("%d ", divisors[i]);
    }
    printf("\n");
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int n = 36; // Example number
    vector<int> divisors;
    int sqrtN = (int)sqrt(n);

    for (int i = 1; i <= sqrtN; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }

    sort(divisors.begin(), divisors.end());

    cout << "Divisors of " << n << ": ";
    for (int d : divisors) {
        cout << d << " ";
    }
    cout << endl;
    return 0;
}

import math

def find_divisors(n):
    divisors = []
    sqrt_n = int(math.isqrt(n))
    for i in range(1, sqrt_n + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors

# Example usage
n = 36
print(f"Divisors of {n}: {find_divisors(n)}")

import java.util.*;

public class Divisors {
    public static List<Integer> findDivisors(int n) {
        List<Integer> divisors = new ArrayList<>();
        int sqrtN = (int)Math.sqrt(n);

        for (int i = 1; i <= sqrtN; i++) {
            if (n % i == 0) {
                divisors.add(i);
                if (i != n / i) {
                    divisors.add(n / i);
                }
            }
        }
        Collections.sort(divisors);
        return divisors;
    }

    public static void main(String[] args) {
        int n = 36;
        List<Integer> result = findDivisors(n);
        System.out.println("Divisors of " + n + ": " + result);
    }
}

function findDivisors(n) {
  const divisors = [];
  const sqrtN = Math.floor(Math.sqrt(n));

  for (let i = 1; i <= sqrtN; i++) {
    if (n % i === 0) {
      divisors.push(i);
      if (i !== n / i) {
        divisors.push(n / i);
      }
    }
  }

  divisors.sort((a, b) => a - b);
  return divisors;
}

const n = 36;
console.log(`Divisors of ${n}:`, findDivisors(n));

package main

import (
	"fmt"
	"math"
	"sort"
)

func findDivisors(n int) []int {
	divisors := []int{}
	sqrtN := int(math.Sqrt(float64(n)))

	for i := 1; i <= sqrtN; i++ {
		if n%i == 0 {
			divisors = append(divisors, i)
			if i != n/i {
				divisors = append(divisors, n/i)
			}
		}
	}
	sort.Ints(divisors)
	return divisors
}

func main() {
	n := 36
	divs := findDivisors(n)
	fmt.Printf("Divisors of %d: %v\n", n, divs)
}

fn find_divisors(n: usize) -> Vec<usize> {
    let mut divisors = Vec::new();
    let sqrt_n = (n as f64).sqrt() as usize;

    for i in 1..=sqrt_n {
        if n % i == 0 {
            divisors.push(i);
            if i != n / i {
                divisors.push(n / i);
            }
        }
    }

    divisors.sort();
    divisors
}

fn main() {
    let n = 36;
    let divisors = find_divisors(n);
    println!("Divisors of {}: {:?}", n, divisors);
}

fun findDivisors(n: Int): List<Int> {
    val divisors = mutableListOf<Int>()
    val sqrtN = kotlin.math.sqrt(n.toDouble()).toInt()
    for (i in 1..sqrtN) {
        if (n % i == 0) {
            divisors.add(i)
            if (i != n / i) {
                divisors.add(n / i)
            }
        }
    }
    divisors.sort()
    return divisors
}

fun main() {
    val n = 36
    val divisors = findDivisors(n)
    println("Divisors of $n: $divisors")
}

import Foundation

func findDivisors(_ n: Int) -> [Int] {
    var divisors = [Int]()
    let sqrtN = Int(Double(n).squareRoot())

    for i in 1...sqrtN {
        if n % i == 0 {
            divisors.append(i)
            if i != n / i {
                divisors.append(n / i)
            }
        }
    }

    divisors.sort()
    return divisors
}

let n = 36
print("Divisors of \(n): \(findDivisors(n))")

function findDivisors(n: number): number[] {
  const divisors: number[] = [];
  const sqrtN = Math.floor(Math.sqrt(n));

  for (let i = 1; i <= sqrtN; i++) {
    if (n % i === 0) {
      divisors.push(i);
      if (i !== n / i) {
        divisors.push(n / i);
      }
    }
  }

  divisors.sort((a, b) => a - b);
  return divisors;
}

const n = 36;
console.log(`Divisors of ${n}:`, findDivisors(n));

Time complexity

Space complexity

O(√n)

In the worst case, we could collect up to 2 × √n divisors before sorting, especially if n has many small factors. Additional space is used for the result list, which grows with the number of divisors.