Делители числа: C++, Python, JavaScript

Иллюстрация: делители числа и программирование на C++, Python и JavaScript

Фактор (делитель) — это число, которое делит заданное число без остатка. Поиск делителей числа с помощью программирования укрепляет понимание циклов, условий и операции взятия остатка (modulo).

В этой статье вы научитесь находить все различные делители натурального числа на C++, Python и JavaScript, сравните простую и оптимизированную стратегии и получите чек-лист для тестирования.

Задача

Дано натуральное число num. Нужно найти и вывести все различные делители числа num.

Примеры:

num = 60 → делители: 1 2 3 4 5 6 10 12 15 20 30 60
num = 100 → делители: 1 2 4 5 10 20 25 50 100
num = 85 → делители: 1 5 17 85

Базовый (наивный) подход

Идея простая:

Перебирать все числа от 1 до num.
Для каждого i проверять, делится ли num на i без остатка (num % i == 0).
Если да — i является делителем, вывести или добавить в список.

Временная сложность: O(n). Память: O(1) (если печатаем по ходу). Такой метод прост, но при больших значениях num будет медленным.

C++ — базовый вариант

// C++ program to find all factors of a natural number
#include 

using namespace std;

void findFactors(int num)
{
    for (int i = 1; i <= num; i++)
    {
        if (num % i == 0)
        {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main()
{
    int num1 = 60;
    cout << "Factors of " << num1 << " are:" << endl;
    findFactors(num1);

    int num2 = 100;
    cout << "Factors of " << num2 << " are:" << endl;
    findFactors(num2);

    int num3 = 85;
    cout << "Factors of " << num3 << " are:" << endl;
    findFactors(num3);

    int num4 = 66;
    cout << "Factors of " << num4 << " are:" << endl;
    findFactors(num4);

    int num5 = 71;
    cout << "Factors of " << num5 << " are:" << endl;
    findFactors(num5);

    return 0;
}

Вывод (пример):

Factors of 60 are:
1 2 3 4 5 6 10 12 15 20 30 60
Factors of 100 are:
1 2 4 5 10 20 25 50 100
Factors of 85 are:
1 5 17 85
Factors of 66 are:
1 2 3 6 11 22 33 66
Factors of 71 are:
1 71

Python — базовый вариант

# Python program to find all factors of a natural number

def findFactors(num):
    for i in range(1, num + 1):
        if num % i == 0:
            print(i, end=" ")
    print()

num1 = 60
print("Factors of", num1, "are:")
findFactors(num1)

num2 = 100
print("Factors of", num2, "are:")
findFactors(num2)

num3 = 85
print("Factors of", num3, "are:")
findFactors(num3)

num4 = 66
print("Factors of", num4, "are:")
findFactors(num4)

num5 = 71
print("Factors of", num5, "are:")
findFactors(num5)

Вывод тот же, что и в примере для C++.

JavaScript — базовый вариант (для браузера)

// JavaScript program to find all factors of a natural number

function findFactors(num) {
  for (let i = 1; i <= num; i++) {
    if (num % i == 0) {
      document.write(i + " ");
    }
  }
  document.write("\n");
}

let num1 = 60;
document.write("Factors of " + num1 + " are:\n");
findFactors(num1);

let num2 = 100;
document.write("Factors of " + num2 + " are:\n");
findFactors(num2);

let num3 = 85;
document.write("Factors of " + num3 + " are:\n");
findFactors(num3);

let num4 = 66;
document.write("Factors of " + num4 + " are:\n");
findFactors(num4);

let num5 = 71;
document.write("Factors of " + num5 + " are:\n");
findFactors(num5);

Оптимизированный подход (с использованием пар делителей)

Наблюдение: делители числа идут попарно — если i делит num, то и num/i тоже делитель. Достаточно перебирать i от 1 до sqrt(num). Для каждого i, делящего num, выводим i и num/i. Если i * i == num — выводим только один раз.

Шаги:

Перебирать i от 1 до floor(sqrt(num)).
Если num % i == 0 — i делитель.
Вторая пара — j = num / i. Если i == j — вывести один раз, иначе вывести оба.

Временная сложность: O(sqrt(n)). Память: O(1) при печати по ходу.

C++ — оптимизированный вариант

// C++ program to find all factors of a natural number (optimized)
#include 
using namespace std;

void findFactors(int num)
{
    for (int i = 1; i <= (int)sqrt(num); i++)
    {
        if (num % i == 0)
        {
            if (num / i == i)
            {
                cout << i << " ";
            }
            else
            {
                cout << i << " " << num / i << " ";
            }
        }
    }
    cout << endl;
}

int main()
{
    int num1 = 60;
    cout << "Factors of " << num1 << " are:" << endl;
    findFactors(num1);

    int num2 = 100;
    cout << "Factors of " << num2 << " are:" << endl;
    findFactors(num2);

    int num3 = 85;
    cout << "Factors of " << num3 << " are:" << endl;
    findFactors(num3);

    int num4 = 66;
    cout << "Factors of " << num4 << " are:" << endl;
    findFactors(num4);

    int num5 = 71;
    cout << "Factors of " << num5 << " are:" << endl;
    findFactors(num5);

    return 0;
}

Пример вывода (пары могут идти в порядке обнаружения):

Factors of 60 are:
1 60 2 30 3 20 4 15 5 12 6 10
Factors of 100 are:
1 100 2 50 4 25 5 20 10
Factors of 85 are:
1 85 5 17
Factors of 66 are:
1 66 2 33 3 22 6 11
Factors of 71 are:
1 71

Важно: Если нужен отсортированный по возрастанию список делителей, оптимизированный вариант требует дополнительной работы — либо сохранять найденные делители в два списка (меньшие и большие) и потом объединять их, либо собирать в набор и сортировать.

Python — оптимизированный вариант

# Python program to find all factors of a natural number (optimized)
import math

def findFactors(num):
    i = 1
    while i <= int(math.sqrt(num)):
        if num % i == 0:
            if num // i == i:
                print(i, end=" ")
            else:
                print(i, num // i, end=" ")
        i += 1
    print()

# Примеры как выше

JavaScript — оптимизированный вариант

// JavaScript program to find all factors of a natural number (optimized)

function findFactors(num) {
  for (let i = 1; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
      if (parseInt(num / i, 10) == i) {
        document.write(i + " ");
      } else {
        document.write(i + " " + parseInt(num / i, 10) + " ");
      }
    }
  }
  document.write("\n");
}

// Примеры как выше

Когда базовый метод непригоден / ограничения

Очень большие значения num (например, > 10^9) — простой перебор до n будет слишком медленным. Используйте оптимизацию O(sqrt(n)) или факторизацию.
Если нужен отсортированный список делителей в порядке возрастания, оптимизированный алгоритм выдаёт пары не в порядке — потребуется дополнительная сортировка или аккуратный сбор в два массива.
В языках с ограничением на целые типы (32-бит) деление больших чисел может потребовать 64-битных типов.

Альтернативный подход: генерация делителей через разложение на простые множители

Идея: разложить num на простые множители (num = p1^a1 p2^a2 …), затем сгенерировать все комбинации степеней этих простых — получим все делители. Это полезно, если нужно многократно запрашивать делители разных чисел, но факторизация сама по себе дороже одной проверки до sqrt(n), если требуется только один раз.

Кому подходит:

Когда требуется получить делители для множества чисел, часто повторно.
Когда нужно перечислить делители в отсортированном порядке (после генерации можно отсортировать список).

Короткая схема (псевдокод):

Выполнить факторизацию числа на простые множители.
Для каждой пары (prime, exponent) перебрать степени 0..exponent.
Перемножать комбинации — получить все делители.

Этот метод даёт контроль над количеством выдаваемых значений и структурой перечисления.

Ментальные модели и эвристики

“Пара делителей”: если i делит n, то j = n / i тоже делитель. Это основная эвристика для O(sqrt(n)).
“Исключение квадрата”: для совершенных квадратов центральный делитель повторяется — выводить один раз.
“Факторизация полезна при множественных запросах”: факторизацию выгодно делать, если потом запрашивать делители часто.

Критерии приёмки (тесты / acceptance)

Тест 1: n = 1 → вывод: 1
Тест 2: простое число (например, 71) → вывод: 1 71
Тест 3: совершенный квадрат (например, 36) → делитель 6 выводится один раз
Тест 4: составное число с несколькими парами (например, 360) → все делители должны присутствовать
Тест 5: очень большое число (по пределам типа данных) — проверить корректность без переполнения

Чек-лист для ролей

Студент: объяснить разницу между O(n) и O(sqrt(n)), написать оба варианта кода и пройти тесты.
Интервьюируемый: уметь быстро описать оптимизацию, упомянуть хранение пар для сортировки.
Разработчик: выбрать подход в зависимости от требований (один вызов — O(sqrt(n)), многократные — факторизация + генерация).

Пример плейбука для получения отсортированных делителей (быстро)

Использовать оптимизированный проход до sqrt(n).
Собрать меньшие делители в массив low (в порядке возрастания), большие в массив high (в порядке убывания).
После цикла объединить low + reversed(high) — получится полный отсортированный список.

Короткий псевдокод:

low = []
high = []
for i in 1..sqrt(n):
- if n % i == 0:
  - if i == n / i: low.append(i)
  - else: low.append(i); high.append(n / i)
result = low + reverse(high)

Decision flowchart (как выбрать метод)

flowchart TD
  A[Нужно ли получить делители] --> B{Будет ли много запросов?}
  B -- Нет --> C[Использовать O'sqrt'n'']
  B -- Да --> D[Факторизовать и генерировать делители]
  C --> E{Нужен отсортированный список?}
  E -- Да --> F[Собирать low/high и объединять]
  E -- Нет --> G[Печатать по ходу]

Приёмо-сдаточные критерии и тесты (примерные тест-кейсы)

Вход: 1 → ожидаемый вывод: [1]
Вход: 2 → [1,2]
Вход: 16 → [1,2,4,8,16] (проверка центрального делителя 4 раз)
Вход: 10^6 (проверка производительности для O(sqrt(n)))

Короткий глоссарий (1 строка)

Делитель (фактор): целое число d, такое что n % d == 0.
Совершенный квадрат: число n = k^2, у которого центральный делитель k повторяется.

Короткое резюме

Для одного запроса используйте оптимизацию до sqrt(n) (O(sqrt(n))).
Для многократных запросов рассмотрите факторизацию и генерацию делителей.
Если нужен отсортированный список — собирайте две части (меньшие и большие делители) и объединяйте.

Важно: всегда проверяйте граничные случаи: 1, простые числа, совершенные квадраты и пределы целочисленного типа.

Как найти все делители числа — C++, Python, JavaScript