Усі дільники (#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=" ")