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

Иллюстрация: поиск делителей числа с помощью C++, Python и JavaScript на фоне образа человеческого мозга

Кратко: в статье объясняется, как находить все делители натурального числа простым и оптимизированным методами. Даны примеры реализации на C++, Python и JavaScript, пояснён алгоритм со сложностью O(n) и оптимизация до O(√n).

Важно: «делитель» (или фактор) — целое число, которое делит заданное число без остатка.

Задача

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

Примеры:

Пример 1: num = 60. Делители: 1 2 3 4 5 6 10 12 15 20 30 60
Пример 2: num = 100. Делители: 1 2 4 5 10 20 25 50 100
Пример 3: num = 85. Делители: 1 5 17 85

Базовый подход

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

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

Временная сложность: O(n). Дополнительная память: O(1).

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

Ниже — оригинальная программа на 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:

# 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)

Вывод (тот же формат):

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

JavaScript (базовый вариант)

Оригинальная программа на 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);

Вывод аналогичен предыдущим примерам.

Оптимизированный подход

Наблюдение: делители числа всегда появляются парами. Для num = 64 это пары (1, 64), (2, 32), (4, 16), (8, 8). Чтобы не проверять все числа до num, достаточно перебирать до √num и выводить обе стороны пары.

Алгоритм:

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

Временная сложность: O(√n). Доп. память: O(1).

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

// C++ program to find all factors of a natural number  
#include   
  
using namespace std;  
  
void findFactors(int num)  
{  
 for(int i=1; i<=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  
import math  
  
def findFactors(num):  
    i = 1  
    while i <= math.sqrt(num):  
        if (num%i==0):  
            if (num/i == i):  
                print(i, end=" ")  
            else:  
                print(i, num//i, end=" ")  
        i = i + 1  
    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)

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

// JavaScript program to find all factors of a natural number  
  
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");  
}  
  
  
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);

Когда подходы не подходят

Очень большие числа: перебор до √n остаётся приемлемым, но при работе с числами > 10^12 нужно учитывать время и арифметику со 64‑битными типами.
Если нужна сортировка делителей по возрастанию, оптимизированный алгоритм требует накопления пар и последующей сортировки или вывода в два прохода (меньшие и большие стороны).
Для факторизации (разложения на простые множители) нужны другие алгоритмы; перечисление всех делителей — не замена факторизации.

Альтернативы и расширения

Использовать хранение пар: при переборе до √n запоминать «большие» делители в стек/массив и выводить их в обратном порядке для сортированного результата.
Для нескольких запросов (множество чисел) выгодно предвычислить таблицу делителей (решето по делителям) до N.
Для нахождения простых множителей — сначала произвести факторизацию (деление на простые) и затем из комбинаций простых множителей получить все делители.

Полезные эвристики

Если num чётное, можно начинать перебор с 1 и 2 и затем шагом 1; но для ускорения можно отдельно проверить 2, а затем перебирать только нечётные i.
Сравнивайте целесообразность памяти и времени: если N небольшое — простой O(n) код проще и понятнее.

Критерии приёмки

Для входа num программа печатает все делители без повторов.
Для простого квадрата (например, 36) центральный делитель (6) выводится ровно один раз.
Порядок вывода не принципиален, если в требованиях нет сортировки.

Набор тестов (acceptance)

Граничные: num = 1 -> [1].
Простое число: num = 71 -> [1, 71].
Полный набор: num = 60 -> [1,2,3,4,5,6,10,12,15,20,30,60].
Квадрат: num = 49 -> [1,7,49] или [1,49,7] в зависимости от реализации, но 7 только один раз.

Краткая шпаргалка (cheat sheet)

Простой метод: проверить i от 1 до num. Сложность O(n).
Оптимальный метод: проверить i от 1 до √num и выводить пары. Сложность O(√n).
Для вывода в порядке возрастания: аккумулируйте большие делители и выведите их в конце в обратном порядке.

Однострочный словарь

Делитель: число, которое делит данное число без остатка.

Итог

Нахождение делителей — простая и полезная задача для отработки базовых конструкций языка и понимания сложности алгоритмов.
Базовый подход прост в реализации, оптимизация через √n обычно достаточна для практических задач.

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

Перебор 1..n — простой, но медленный (O(n)).
Перебор 1..√n — быстрый и стандартный прием (O(√n)).
Для больших входов рассматривайте предвычисления или специализированные алгоритмы факторизации.