prime factorization Algorithm
In number theory, integer factorization is the decomposition of a composite number into a merchandise of smaller integers. When they are both large, for case more than two thousand bits long, randomly choose, and about the same size (but not too near, for example, to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the primes being factored increases, the number of operations need to perform the factorization on any computer increases drastically.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Declaring variables for maintaing prime numbers and to check whether a number is prime or not
bool isprime[1000006];
vector<int> prime_numbers;
vector<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(make_pair(prime_numbers[i], count));
}
}
/*
I added a simple UI.
*/
int main()
{
int num;
cout << "\t\tComputes the prime factorization\n\n";
cout << "Type in a number: ";
cin >> num;
SieveOfEratosthenes(num);
prime_factorization(num);
// Prime factors with their powers in the given number in new line
for (auto it : factors)
{
cout << it.first << " " << it.second << endl;
}
return 0;
}
