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

Факторизация числа

Разложение числа на простые множители за O(√n)

🐍 Python
def factorize(n):
    d = 2
    p = []
    while d * d <= n:
        while n % d == 0:
            p.append(d)
            n //= d
        d += 1
    if n > 1:
        p.append(n)
    return p

n = int(input())
print(*factorize(n))
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

vector<long long> factorize(long long n) {
    vector<long long> p;
    long long d = 2;
    while (d * d <= n) {
        while (n % d == 0) {
            p.push_back(d);
            n /= d;
        }
        d++;
    }
    if (n > 1) {
        p.push_back(n);
    }
    return p;
}

int main() {
    long long n;
    cin >> n;
    
    vector<long long> factors = factorize(n);
    for (long long x : factors) {
        cout << x << " ";
    }
    
    return 0;
}

Как разложить число на простые множители?

Факторизация — это разложение числа на произведение простых множителей.

Алгоритм

  1. Проверяем делители от 2 до √n
  2. Если число делится на d, добавляем d в список и делим число на d, пока делится
  3. Переходим к следующему d
  4. Если после проверки всех делителей осталось число > 1, оно простое — добавляем его

Пример

Для n = 84:

Результат: 2, 2, 3, 7 (84 = 2²·3·7)

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

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

Ввод: целое число n (n ≥ 2)

Вывод: простые множители в порядке возрастания

Пример:

84

Вывод: 2 2 3 7

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

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