Розклад на множники (Розбір)

Розклад на множники#11611

Оскільки потрібно факторизувати багато чисел, що не перевищують $1 0^{7}$ 10^7, вигідно виконати попереднє обчислення. За допомогою модифікованого решета Ератосфена побудуємо масив $s p f$ (smallest prime factor), де

$s p f [i]$ містить найменший простий дільник числа $i$

Факторизація числа $n$ виконується наступним чином. Поки $n > 1$ n > 1, беремо $p = s p f [n]$ p = spf[n], найменший простий дільник поточного значення $n$ , і ділимо $n$ на $p$ , поки ділення виконується націло, підраховуючи показник степеня. Потім виводимо множник $p$ у відповідному степені та переходимо до наступного простого дільника. Прості множники при цьому отримуються у порядку зростання, що відповідає необхідному формату виведення.

Побудова решета вимагає $O (n l o g l o g n)$ O(n~log~log~n) часу. Кожне ділення зменшує $n$ щонайменше удвічі, тому факторизація одного числа виконується за $O (l o g n)$ O(log~n). Загальна часова складність для $q$ запитів становить $O (n l o g l o g n + q l o g n)$ O(n~log~log~n + q~log~n).

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

Оголосимо масив $s p f$ , у якому $s p f [i]$ містить найменший простий дільник числа $i$ .

#define MAX 10000001
int spf[MAX + 1];

Функція Sieve реалізує решето Ератосфена та заповнює масив $s p f$ .

void Sieve(int n)
{
  for (int i = 0; i < n; i++)
    spf[i] = i;
  for (int i = 2; i <= sqrt(n); i++)
    if (spf[i] == i)
      for (int j = i * i; j < n; j += i)
        if (spf[j] == j) spf[j] = i;
}

C++

Функція factorize розкладає число $n$ на прості множники, використовуючи масив $s p f$ .

void factorize(int n)
{

Виділяємо прості множники з числа $n$ , поки воно більше $1$ .

  while (n > 1)
  {

Найменший простий дільник числа $n$ дорівнює $p$ .

    int p = spf[n];

Знаходимо максимальний степінь $p o w er$ , для якого $p^{p o w er}$ p^{power} ділить число $n$ .

    int power = 0;
    while (n % p == 0)
    {
      n /= p;
      power++;
    }

Виводимо множник $p^{p o w er}$ p^{power}.

    if (power > 1) printf("%d^%d", p, power); else printf("%d", p);

Між множниками слід виводити знак ' $*$ '.

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

Основна частина програми. Заповнюємо масив $s p f$ , використовуючи решето Ератосфена.

Sieve(MAX);

Для кожного вхідного значення $n$ виводимо його розклад на прості множники.

while (scanf("%d", &n) == 1)
  factorize(n);