Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Basics

All Divisors

Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Print all divisors of n in increasing order, separated by spaces.

Input

One integer n.

Output

The divisors in ascending order.

Constraints

Loop only up to √n: every divisor d below √n pairs with n / d.

Example 1

Input

12

Output

1 2 3 4 6 12

Example 2

Input

7

Output

1 7

Hints

  1. Every divisor d ≤ √n has a partner n / d ≥ √n.
  2. Collect the small divisors in one list and their partners in another, then print small ones followed by the partners reversed. Don't print √n twice.

Approach

Loop d from 1 while d * d <= n. When d divides n, d goes into the "small" list and n / d into the "large" list (unless both are the same, as when n is a perfect square). Small divisors come out in increasing order and large ones in decreasing order, so print small followed by reversed large. That's at most about 31 623 steps for n = 10^9.

Complexity: O(√n) time · O(number of divisors) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    vector<long long> small, large;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            small.push_back(d);
            if (d != n / d) large.push_back(n / d);
        }
    }
    reverse(large.begin(), large.end());
    small.insert(small.end(), large.begin(), large.end());
    for (size_t i = 0; i < small.size(); i++) cout << small[i] << (i + 1 < small.size() ? " " : "\n");
    return 0;
}

Python solution

n = int(input())
small, large = [], []
d = 1
while d * d <= n:
    if n % d == 0:
        small.append(d)
        if d != n // d:
            large.append(n // d)
    d += 1
print(*(small + large[::-1]))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        List<Long> small = new ArrayList<>(), large = new ArrayList<>();
        for (long d = 1; d * d <= n; d++) {
            if (n % d == 0) {
                small.add(d);
                if (d != n / d) large.add(n / d);
            }
        }
        Collections.reverse(large);
        small.addAll(large);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < small.size(); i++) sb.append(i > 0 ? " " : "").append(small.get(i));
        System.out.println(sb);
    }
}

Solve All Divisors online · All practice problems