Разложение числа на множители

Задачи и их решение / Разложение числа на множители

Онлайн разложение на множители

Введите число:


Всякое число можно разложить на простые множители. При этом получается одно и то же разложение,
если не учитывать порядка записи множителей.
Последовательность действий, которые выполняют при разложении числа на простые множители в математике:

  • Проверить, не является ли предложенное число простым.
  • Если нет, то подобрать, руководствуясь признаками деления, делитель, из простых чисел начиная с наименьшего (2, 3, 5 …).
  • Повторить это действие до тех пор, пока частное не окажется простым числом.

Для определения простоты числа можно использовать алгоритм "Решето Эратосфена".
Разложение числа на простые множители в программировании осуществляется аналогичным способом:

    • Задать начальное значение делителя равным 2.
    • Проверить, делится ли число на делитель. Если да, записать делитель в список множителей и разделить число на делитель.
    • Повторить предыдущий шаг пока выполняется условие кратности.
    • Перейти к следующему делителю (в простейшем случае увеличить делитель на 1)
    • Вычисления закончить когда частное от деления станет равным 1

.

Реализация

#include <iostream>
using namespace std;
int main() {
  int n, div = 2;
  cout << "N = ";
  cin >> n;
  cout << n << " = 1";
  while (n > 1) {
    while (n % div == 0) {
      cout << " * " << div;
      n = n / div;
    }
    div++;
  }
  cin.get(); cin.get();
  return 0;
}

Результат выполнения

Разложение на простые множители

Если учесть, что из четных простых делителей числа может быть только 2, то можно уменьшить количество циклов в реализации алгоритма, добавив дополнительную проверку

#include <iostream>
using namespace std;
int main() {
  int n, div = 2;
  cout << "N = ";
  cin >> n;
  cout << n << " = 1";
  while (n > 1) {
     while (n % div == 0) {
      cout << " * " << div;
      n = n / div;
    }
     if (div == 2)  div++;
     else div += 2;
  }
  cin.get(); cin.get();
  return 0;
}

Алгоритм разложения на простые множители также можно реализовать с использованием рекурсии:

#include <iostream>
using namespace std;
void find(int n, int div) {
  if (n == 1) return;
  if (n%div == 0) {
    cout << " * " << div;
    find(n / div, div);
  } else
    if (div == 2)
      find(n, div + 1);
    else
      find(n, div + 2);
}
int main() {
  int n, div = 2;
  cout << "N = ";
  cin >> n;
  cout << n << " = 1";
  find(n, 2);
  cin.get(); cin.get();
  return 0;
}

Назад


Назад: Задачи и их решение

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *