Урок математики#572

Урок математики (Розбір)

У задачі потрібно розкласти число $n$ на прості множники, тобто подати його у вигляді $n = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot ... \cdot p_{k}^{a_{k}}$ n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}, де $p_{1} < p_{2} < ... < p_{k}$ p_1 < p_2 < ... < p_k — прості числа. Кожен простий дільник $p_{i}$ p_i виводиться разом зі своїм степенем $a_{i}$ a_i, якщо $a_{i} > 1$ a_i > 1.

Будемо перебирати можливі дільники $i$ у порядку зростання, починаючи з $2$ . Якщо $i$ ділить $n$ , то ділимо $n$ на $i$ доти, доки ділення виконується націло, і підраховуємо кількість ділень $c$ . Отримане значення $c$ і є степенем, з яким $i$ входить до розкладу. Після цього виводимо $i$ , якщо $c = 1$ c = 1, або $i^{c}$ i^c, якщо $c > 1$ c > 1.

Перебір дільників достатньо вести до $n$ \sqrt{n}. Якщо у числа немає дільників у проміжку від $2$ до $n$ \sqrt{n}, то це число просте. Тому після завершення циклу поточне значення $n$ або дорівнює $1$ , або є простим числом — останнім множником розкладу, який також потрібно вивести. Такий "великий" множник може бути лише один: добуток двох множників, більших за $n$ \sqrt{n}, перевищує $n$ .

Приклад. Розглянемо $n = 3240$ n = 3240.

$i = 2 : 3240 \to 1620 \to 810 \to 405, c = 3$ i = 2: 3240 \to 1620 \to 810 \to 405, c = 3. Виводимо $2^{3} *$ 2^3*, оскільки $n = 405 > 1$ n = 405 > 1.
$i = 3 : 405 \to 135 \to 45 \to 15 \to 5, c = 4$ i = 3: 405 \to 135 \to 45 \to 15 \to 5, c = 4. Виводимо $3^{4} *$ 3^4*, оскільки $n = 5 > 1$ n = 5 > 1.
$i = 4 : 4 \cdot 4 > 5$ i = 4: 4 \cdot 4 > 5, цикл завершується.

Залишок $n = 5 > 1$ n = 5 > 1 є простим множником, виводимо $5$ .

Відповідь: $2^{3} * 3^{4} * 5$ 2^3*3^4*5.

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

Функція factor виконує розклад числа $n$ на прості множники.

void factor(int n)
{
  for (int i = 2; i <= sqrt(n); i++)
  {
    if (n % i) continue;

Число $i$ є дільником $n$ . У змінній $c$ підрахуємо степінь, з яким воно входить до розкладу $n$ .

    int c = 0;
    while (n % i == 0) n /= i, c++;

Виводимо множник $i^{c}$ i^c. Якщо степінь множника $c = 1$ c = 1, виводимо лише $i$ . В іншому випадку виводимо множник $i$ з його степенем.

    if (c > 1) printf("%d^%d",i,c); else printf("%d",i);

Якщо число $n$ ще не розкладено повністю $(n > 1)$ (n > 1), виводимо знак множення.

    if (n > 1) printf("*");
  }

Якщо після завершення циклу значення $n$ більше за $1$ , то воно є простим.

  if (n > 1) printf("%d",n);
  printf("\n");
}

Основна частина програми. Читаємо вхідне число $n$ і запускаємо його факторизацію.

scanf("%d",&n);
factor(n);

Python реалізація

import math

Функція factor виконує розклад числа $n$ на прості множники.

def factor(n):
  for i in range(2, math.isqrt(n) + 1):
    if n % i: continue

Число $i$ є дільником $n$ . У змінній $c$ підрахуємо степінь, з яким воно входить до розкладу $n$ .

    c = 0
    while n % i == 0:
      n //= i
      c += 1

    if c > 1: print(i,"^",c, sep = "", end="")
    else: print(i, end="")

Якщо число $n$ ще не розкладено повністю $(n > 1)$ (n > 1), виводимо знак множення.

    if n > 1: print("*", end="")

Якщо після завершення циклу значення $n$ більше за $1$ , то воно є простим.

  if n > 1: print(n)
  else: print()

Основна частина програми. Читаємо вхідне число $n$ і запускаємо його факторизацію.

n = int(input())
factor(n)