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

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

 

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

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


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

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

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

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

Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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, то можно уменьшить количество циклов в реализации алгоритма, добавив дополнительную проверку

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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 не будет опубликован. Обязательные поля помечены *