Problem

Given a natural number n, list all distinct positive divisors (factors) of n.

Input: a single integer n (assume n >= 1).

Output: all divisors of n (we will show multiple methods; one prints in arbitrary order, one prints sorted).

Examples

Example 1

1
2

Input: n = 10
Output: 1 2 5 10

Example 2

1
2

Input: n = 100
Output: 1 2 4 5 10 20 25 50 100

Example 3

1
2

Input: n = 125
Output: 1 5 25 125

Notes

  • There is no exact single LeetCode problem that is simply “list all divisors of n”, but related number-theory problems and divisor-queries are common.
Similar Problems

Solution

We present three methods:

  • Method 1 — Brute force check (O(n)).
  • Method 2 — Check up to sqrt(n) and output pairs (O(sqrt(n))).
  • Method 3 — Check up to sqrt(n) and collect halves to print in sorted order (O(sqrt(n))).

Method 1 — Brute force

Intuition

Check every integer i from 1 to n and test whether i divides n.

Approach

  1. For i from 1 to n:
    • If n % i == 0, output i.

Edge cases: n == 1 returns 1.

Code

1
2
3
4
5
6
7
8

class Solution {
 public:
  static void printDivisorsBrute(int n) {
    for (int i = 1; i <= n; ++i) {
      if (n % i == 0) std::printf("%d ", i);
    }
  }
};
1
2
3
4
5
6
7

package main
import "fmt"
func PrintDivisorsBrute(n int) {
  for i := 1; i <= n; i++ {
    if n%i == 0 { fmt.Printf("%d ", i) }
  }
}
1
2
3
4
5

class Solution {
  public static void printDivisorsBrute(int n) {
    for (int i = 1; i <= n; ++i) if (n % i == 0) System.out.printf("%d ", i);
  }
}
1
2
3
4
5

object Solution {
  fun printDivisorsBrute(n: Int) {
    for (i in 1..n) if (n % i == 0) print("$i ")
  }
}
1
2
3
4
5

class Solution:
    def print_divisors_brute(self, n: int) -> None:
        for i in range(1, n+1):
            if n % i == 0:
                print(i, end=' ')
1
2
3
4
5
6

pub struct Solution;
impl Solution {
  pub fn print_divisors_brute(n: i64) {
    for i in 1..=n { if n % i == 0 { print!("{} ", i); } }
  }
}

Complexity

  • ⏰ Time complexity: O(n) — tests every integer up to n.
  • 🧺 Space complexity: O(1).

Method 2 — Check up to sqrt(n) and output pairs

Intuition

Divisors come in pairs (i, n/i). If i <= sqrt(n) and i divides n, then n/i is the corresponding larger divisor.

Approach

  1. For i from 1 to floor(sqrt(n)):
    • If n % i == 0: output i.
      • If n / i != i, also output n / i (this prints a large counterpart).

Note: output order is not sorted (small then its paired large), producing a zig-zag pattern.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
 public:
  static void printDivisorsPairs(int n) {
    int r = (int) std::floor(std::sqrt(n));
    for (int i = 1; i <= r; ++i) {
      if (n % i == 0) {
        if (n / i == i) std::printf("%d ", i);
        else std::printf("%d %d ", i, n / i);
      }
    }
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main
import ("fmt"; "math")
func PrintDivisorsPairs(n int) {
  r := int(math.Floor(math.Sqrt(float64(n))))
  for i := 1; i <= r; i++ {
    if n%i == 0 {
      if n/i == i { fmt.Printf("%d ", i) } else { fmt.Printf("%d %d ", i, n/i) }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
  public static void printDivisorsPairs(int n) {
    int r = (int)Math.floor(Math.sqrt(n));
    for (int i = 1; i <= r; ++i) {
      if (n % i == 0) {
        if (n / i == i) System.out.printf("%d ", i);
        else System.out.printf("%d %d ", i, n / i);
      }
    }
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

object Solution {
  fun printDivisorsPairs(n: Int) {
    val r = kotlin.math.sqrt(n.toDouble()).toInt()
    for (i in 1..r) {
      if (n % i == 0) {
        if (n / i == i) print("$i ") else print("$i ${n / i} ")
      }
    }
  }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def print_divisors_pairs(self, n: int) -> None:
        r = int(n**0.5)
        for i in range(1, r+1):
            if n % i == 0:
                if n // i == i:
                    print(i, end=' ')
                else:
                    print(i, n//i, end=' ')
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

pub struct Solution;
impl Solution {
  pub fn print_divisors_pairs(n: i64) {
    let r = (n as f64).sqrt().floor() as i64;
    for i in 1..=r {
      if n % i == 0 {
        if n / i == i { print!("{} ", i); } else { print!("{} {} ", i, n / i); }
      }
    }
  }
}

Complexity

  • ⏰ Time complexity: O(sqrt(n)) — loop up to sqrt(n).
  • 🧺 Space complexity: O(1).

Method 3 — Print divisors in sorted order (recommended)

Intuition

Collect the small divisors while iterating up to sqrt(n) and save their large counterparts; then print small divisors followed by the reversed list of large divisors to produce a sorted sequence.

Approach

  1. Initialize an empty list highs.
  2. For i from 1 to floor(sqrt(n)):
    • If n % i == 0:
      • If n / i == i, print i.
      • Else: print i and append n / i to highs.
  3. After the loop, iterate highs in reverse and print each element.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
class Solution {
 public:
  static void printDivisorsSorted(int n) {
    std::vector<int> highs;
    int r = (int) std::floor(std::sqrt(n));
    for (int i = 1; i <= r; ++i) {
      if (n % i == 0) {
        if (n / i == i) std::printf("%d ", i);
        else { std::printf("%d ", i); highs.push_back(n / i); }
      }
    }
    for (int i = (int)highs.size() - 1; i >= 0; --i) std::printf("%d ", highs[i]);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main
import ("fmt"; "math")
func PrintDivisorsSorted(n int) {
  highs := []int{}
  r := int(math.Floor(math.Sqrt(float64(n))))
  for i := 1; i <= r; i++ {
    if n%i == 0 {
      if n/i == i { fmt.Printf("%d ", i) }
      else { fmt.Printf("%d ", i); highs = append(highs, n/i) }
    }
  }
  for i := len(highs)-1; i >= 0; i-- { fmt.Printf("%d ", highs[i]) }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
  public static void printDivisorsSorted(int n) {
    List<Integer> highs = new ArrayList<>();
    int r = (int)Math.floor(Math.sqrt(n));
    for (int i = 1; i <= r; ++i) {
      if (n % i == 0) {
        if (n / i == i) System.out.printf("%d ", i);
        else { System.out.printf("%d ", i); highs.add(n / i); }
      }
    }
    for (int i = highs.size() - 1; i >= 0; --i) System.out.printf("%d ", highs.get(i));
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

object Solution {
  fun printDivisorsSorted(n: Int) {
    val highs = mutableListOf<Int>()
    val r = kotlin.math.sqrt(n.toDouble()).toInt()
    for (i in 1..r) {
      if (n % i == 0) {
        if (n / i == i) print("$i ") else { print("$i "); highs.add(n / i) }
      }
    }
    for (i in highs.size - 1 downTo 0) print("${highs[i]} ")
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def print_divisors_sorted(self, n: int) -> None:
        highs = []
        r = int(n**0.5)
        for i in range(1, r+1):
            if n % i == 0:
                if n // i == i:
                    print(i, end=' ')
                else:
                    print(i, end=' ')
                    highs.append(n//i)
        for x in reversed(highs): print(x, end=' ')
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

pub struct Solution;
impl Solution {
  pub fn print_divisors_sorted(n: i64) {
    let mut highs: Vec<i64> = Vec::new();
    let r = (n as f64).sqrt().floor() as i64;
    for i in 1..=r {
      if n % i == 0 {
        if n / i == i { print!("{} ", i); }
        else { print!("{} ", i); highs.push(n / i); }
      }
    }
    for &x in highs.iter().rev() { print!("{} ", x); }
  }
}

Complexity

  • ⏰ Time complexity: O(sqrt(n)) — iterate up to sqrt(n).
  • 🧺 Space complexity: O(sqrt(n)) for storing large divisors in worst-case (Method 3).