Усі дільники#8669

Усі дільники (Розбір)

Якщо $i$ — дільник числа $n$ , то $n / i$ також є дільником числа $n$ . При цьому якщо $n$ — повний квадрат, то дільники $n$ \sqrt{n} і $n / n$ n /\sqrt{n} співпадають.

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

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

scanf("%d",&n);

Перебираємо дільники від $1$ до $n$ \sqrt{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$ \sqrt{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();
  }
}

Java

Python реалізація

import math