8669. Все делители

Найдите все делители натурального числа n.

Вход. Одно натуральное число n (n ≤ 10⁹).

Выход. Выведите в возрастающем порядке все делители числа n.

Пример входа 1	Пример выхода 1
10	1 2 5 10
Пример входа 2	Пример выхода 2
36	1 2 3 4 6 9 12 18 36

РЕШЕНИЕ

делители числа

Анализ алгоритма

Если i – делитель числа n, то n / i также является делителем числа n. При этом если n – полный квадрат, то делители и n / совпадают.

Реализация алгоритма

Читаем входное значение n.

scanf("%d",&n);

Перебираем делители от 1 до не включительно.

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

if (n % i == 0)

{

Если i – делитель числа n, то n / i также будет делителем числа n.

v.push_back(i);

v.push_back(n / i);

}

Проверяем, является ли n полным квадратом. В этом случае добавляем в вектор делитель .

i = sqrt(n);

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

Сортируем делители в возрастающем порядке.

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

Выводим в одной строке все делители.

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

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

printf("\n");

Java реализация

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 реализация

import math

Читаем входное значение n.

n = int(input())

В список lst будем добавлять делители числа n.

lst = []

Перебираем делители от 1 до не включительно.

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

Если i – делитель числа n, то n / i также будет делителем числа n.

if n % i == 0:

lst.append(i)

lst.append(n//i)

Проверяем, является ли n полным квадратом. В этом случае добавляем в вектор делитель .

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

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

Сортируем делители в возрастающем порядке.

lst.sort()

Выводим в одной строке все делители.

print(*lst)