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