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
- 1 ≤ n ≤ 10^9
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
- Every divisor d ≤ √n has a partner n / d ≥ √n.
- 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);
}
}