8669. All divisors

Find all divisors of a positive integer n.

Input. One positive integer n (n ≤ 10⁹).

Output. Print all divisors of n in ascending order.

Sample input 1	Sample output 1
10	1 2 5 10
Sample input 2	Sample output 2
36	1 2 3 4 6 9 12 18 36

SOLUTION

divisors of a number

Algorithm analysis

If i is a divisor of n, then n / i is also a divisor of n. Moreover, if n is a perfect square, then the divisors and n / are the same.

Algorithm implementation

Read the input value of n.

scanf("%d",&n);

Iterate over divisors from 1 to not inclusive.

for(i = 1; i < sqrt(n); i++)

if (n % i == 0)

{

If i is a divisor of n, then n / i is also a divisor of n.

v.push_back(i);

v.push_back(n / i);

}

Check if n is a perfect square. In this case, add the divisor to the vector.

i = sqrt(n);

if (i * i == n) v.push_back(i);

Sort the divisors in ascending order.

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

Print all divisors in one line.

for(i = 0; i < v.size(); i++)

printf("%d ",v[i]);

printf("\n");

Java implementation

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<Integer> v = new ArrayList<Integer>();

for(int i = 1; i < Math.sqrt(n); i++)

if (n % i == 0)

{

v.add(i);

v.add(n / i);

}

int i = (int)Math.sqrt(n);

if (n % i == 0) v.add(i);

Collections.sort(v);

for(i = 0; i < v.size(); i++)

System.out.print(v.get(i) + " ");

System.out.println();

con.close();

}

}

Python implementation

import math

Read the input value of n.

n = int(input())

We’ll add the divisors of n to the list lst.

lst = []

Iterate over divisors from 1 to not inclusive.

for i in range(1,int(math.sqrt(n))):

If i is a divisor of n, then n / i is also a divisor of n.

if n % i == 0:

lst.append(i)

lst.append(n//i)

Check if n is a perfect square. In this case, add the divisor to the vector.

i = int(math.sqrt(n));

if n % i == 0: lst.append(i);

Sort the divisors in ascending order.

lst.sort()

Print all divisors in one line.

print(*lst)