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

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

 

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

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


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

  • Проверить, не является ли предложенное число простым.
  • Если нет, то подобрать, руководствуясь признаками деления, делитель, из простых чисел начиная с наименьшего (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;
}

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

Комментариев к записи: 3

  • Здравствуйте. Очень полезная статья. Однако для защиты курсового проекта, преподаватель требует модифицировать программу таким образом, чтобы на первом этапе, используя решето Эратосфена генерировалась таблица простых чисел, после чего, с их помощью выполнялось разложения на множители. Блок-схему нашел (не знаю нужна ли она Вам, но на всякий случай даю ссылку: http://www.mathros.net.ua/rozkladannja-chysel-na-prosti-mnozhnyky.html). Если Вам не трудно помогите с реализацией. Программирование на языке С ++, не самый сильный мой конек !!!

  • Удод Подстольный
    ваша последняя программа в качестве результата при больших числах выдает всегда одно и то же 1*2*2*5*13*41*61*1321 и пишет что переменные читаются

    • Николи nickname
      Hi all привет & здрасьте. хочу вас узнать или просить проверить результаты, мои задачи, вот часто ли 2^64"k + 1 является числом простым. Всё всем гудбай; чао.

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

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