С++ решето Эратосфена

Решето Эратосфена — эффективный алгоритм для нахождения всех простых чисел до заданного предела. В задаче факторизации числа этот алгоритм помогает предварительно определить список простых делителей, которые затем используются для разложения числа на простые множители методом простого перебора.

## Шаги решения задачи

1. **Ввод числа для факторизации**: Программа запрашивает у пользователя число, которое требуется разложить на простые множители.

2. **Генерация списка простых чисел**: Используя решето Эратосфена, генерируется список всех простых чисел до квадратного корня из данного числа. Это оптимизирует процесс факторизации, так как достаточно проверять делители только до корня числа.

3. **Факторизация методом простого перебора**:
- Перебираются все сгенерированные простые числа.
- Для каждого простого числа проверяется, делит ли оно заданное число.
- Если делит, то этот простой делитель записывается, и число делится на него столько раз, пока деление возможно. Это позволяет определить кратность каждого простого множителя.
- Если после перебора всех простых чисел остается число больше 1, оно само является простым множителем.

4. **Вывод результата**: Программа выводит все найденные простые множители и их кратности.

## Реализация на C++ https://codeshare.io/deo4ye

## Пояснение к коду

1. **Функция `sieveOfEratosthenes`**:
- Принимает максимальное число `max`, до которого нужно найти простые числа.
- Создаёт булевый вектор `is_prime`, инициализируя все позиции как `true`.
- Проходит по всем числам от 2 до `sqrt(max)`. Если число простое, то все его кратные помечаются как составные.
- В конце собирает все числа, которые остались простыми, в вектор `primes` и возвращает его.

2. **Функция `factorize`**:
- Принимает число `n` для факторизации и список простых чисел `primes`.
- Проверяет, делится ли `n` на каждый простой делитель. Если делится, определяет кратность делителя и выводит его.
- После перебора всех простых делителей, если осталось число больше 1, оно само является простым множителем и выводится.
- Если не найдено ни одного делителя, выводится сообщение, что число простое.

3. **Функция `main`**:
- Запрашивает у пользователя ввод числа для факторизации.
- Вычисляет верхнюю границу для решета Эратосфена как квадратный корень из числа плюс один.
- Генерирует список простых чисел с помощью `sieveOfEratosthenes`.
- Вызывает функцию `factorize` для разложения числа на простые множители.

## Пример работы программы

```
Введите число для факторизации: 360
Факторизация числа 360:
2^3 3^2 5
```

В этом примере число `360` разложено на простые множители: \( 2^3 \times 3^2 \times 5 \).

## Дополнительные замечания

- **Оптимизация решета**: Для больших чисел генерация решета до `sqrt(n)` достаточно эффективна для большинства практических задач. Однако для очень больших чисел существуют более оптимальные алгоритмы факторизации.

- **Тип данных**: В программе используется тип `long long` для переменной `n`, что позволяет обрабатывать числа до примерно \(9 \times 10^{18}\). Если требуется работать с ещё большими числами, потребуется использовать специализированные библиотеки для работы с большими целыми числами.

- **Обработка ошибок**: В программе предусмотрена базовая проверка на ввод числа меньше 2, так как числа 0 и 1 не имеют разложения на простые множители.

Надеюсь, это объяснение и пример помогут вам реализовать факторизацию числа на C++ с использованием решета Эратосфена. Если у вас возникнут дополнительные вопросы, не стесняйтесь обращаться!