#### Prime Factorization

m
S
```/**
* @file
* @brief Prime factorization of positive integers
*/
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

/** Declaring variables for maintaing prime numbers and to check whether a
* number is prime or not
*/
bool isprime[1000006];

/** list of prime numbers */
std::vector<int> prime_numbers;

/** list of prime factor-pairs */
std::vector<std::pair<int, int>> factors;

/** Calculating prime number upto a given range
*/
void SieveOfEratosthenes(int N) {
// initializes the array isprime
memset(isprime, true, sizeof isprime);

for (int i = 2; i <= N; i++) {
if (isprime[i]) {
for (int j = 2 * i; j <= N; j += i) isprime[j] = false;
}
}

for (int i = 2; i <= N; i++) {
if (isprime[i])
prime_numbers.push_back(i);
}
}

/** Prime factorization of a number */
void prime_factorization(int num) {
int number = num;

for (int i = 0; prime_numbers[i] <= num; i++) {
int count = 0;

// termination condition
if (number == 1) {
break;
}

while (number % prime_numbers[i] == 0) {
count++;
number = number / prime_numbers[i];
}

if (count)
factors.push_back(std::make_pair(prime_numbers[i], count));
}
}

/** Main program */
int main() {
int num;
std::cout << "\t\tComputes the prime factorization\n\n";
std::cout << "Type in a number: ";
std::cin >> num;

SieveOfEratosthenes(num);

prime_factorization(num);

// Prime factors with their powers in the given number in new line
for (auto it : factors) {
std::cout << it.first << " " << it.second << std::endl;
}

return 0;
}
```