← Назад к математике

Количество делителей числа

Подсчёт количества натуральных делителей числа

🐍 Python

x = int(input())
i = 1
c = 0
while i * i <= x:
    if x % i == 0 and i * i != x:
        c += 2
    elif i * i == x and x % i == 0:
        c += 1
    i += 1
print(c)

⚙️ C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x;
    cin >> x;
    
    long long i = 1, c = 0;
    while (i * i <= x) {
        if (x % i == 0 && i * i != x) {
            c += 2;
        } else if (i * i == x && x % i == 0) {
            c += 1;
        }
        i++;
    }
    
    cout << c << endl;
    return 0;
}

Как подсчитать количество делителей?

Делители числа идут парами: если d — делитель n, то n/d — тоже делитель. Исключение — случай, когда d = n/d (то есть d² = n).

Алгоритм

Перебираем i от 1 до √n
Если i делит n:
- Если i² = n → добавляем 1 делитель (i)
- Иначе → добавляем 2 делителя (i и n/i)

Пример

Для n = 12: делители 1, 2, 3, 4, 6, 12 → всего 6 делителей.

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

Если n = p₁^{k₁}·p₂^{k₂}·...·pₘ^{kₘ}, то количество делителей = (k₁+1)·(k₂+1)·...·(kₘ+1)

Формат ввода и вывода

Ввод: целое число x (x ≥ 1)

Вывод: количество делителей

Пример:

Вывод: 6

Попробовать онлайн

Число x:

Результат появится здесь...