Prime factorization with occurance count

This is a program written in C++ to find the prime factors of a number and the occurance it has made in the prime factorization.

//Program for Prime Factorization
using namespace std;

typedef pair<int,int> PFs;

int main(){
	int n;
	vector<PFs> vec;
	int i;
	for( i = 2; i * i <= n; i++){
		if(n % i ==0){
			int count=0;
			while(n % i ==0){
	auto it=vec.begin();
		cout<<(*it).first<<" "<<(*it).second<<endl;

We are iterating i from 2 to (n)^1/2, whenever we find the smallest factor, which will most definitely be prime (as we are starting from 2 itself), we will count it occurance by dividing and updating n by (n/i). This continues until we are remaining with either n>1 or n=1.
If n=1, this would mean that the last prime factor is still remaining, we will therefore know that the last factor must be the remaining n itself, and the number of occurance of this number would be 1.

1 Like