47 lines
1.1 KiB
C++
47 lines
1.1 KiB
C++
/*
|
||
* Задание 2
|
||
* Написать программу для факторизации заданного с клавиатуры числа
|
||
* методом простого перебора (указать простые множители и их кратность).
|
||
* Для анализа числа на простоту использовать решето Эратосфена/
|
||
*/
|
||
|
||
#include <iostream>
|
||
#include <vector>
|
||
#include <map>
|
||
|
||
#include "sieveoferatosthenes.cpp"
|
||
|
||
// Функция для факторизации числа (метод простого перебора)
|
||
std::map<int, int> factorize(int number) {
|
||
std::map<int, int> factors;
|
||
std::vector<int> primes = sieveOfEratosthenes(number);
|
||
|
||
for (int prime : primes) {
|
||
if (prime * prime > number) break;
|
||
while (number % prime == 0) {
|
||
factors[prime]++;
|
||
number /= prime;
|
||
}
|
||
}
|
||
if (number > 1) {
|
||
factors[number]++;
|
||
}
|
||
|
||
return factors;
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int n;
|
||
std::cin >> n;
|
||
|
||
auto factors = factorize(n);
|
||
|
||
for (const auto& factor : factors) {
|
||
std::cout << factor.first << " : " << factor.second << "\n";
|
||
}
|
||
|
||
return 0;
|
||
}
|
||
|