Все делители (#8669)

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

Если $i$ – делитель числа $n$ , то $\frac{n}{i}$ также будет делителем числа $n$ . При этом если $n$ – полный квадрат, то делители $n$ и $\frac{n}{n}$ совпадают.

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

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

scanf("%d",&n);

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

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$ полным квадратом. В этом случае добавляем в вектор делитель $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 = int(input())
list = []
for i in range(1, int(math.sqrt(n))):
    if n % i == 0:
        list.append(i)
        list.append(n//i)

i = int(math.sqrt(n));
if n % i == 0: list.append(i);

list.sort()
print(*list, sep=" ")