/*
 * Задание 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;
}