Prime factorization with occurance count

general
,
1

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
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PFs;

int main(){
	int n;
	cin>>n;
	
	vector<PFs> vec;
	int i;
	
	for( i = 2; i * i <= n; i++){
		
		if(n % i ==0){
			int count=0;
			while(n % i ==0){
				
				n/=i;
				count++;
			}
			vec.push_back({i,count});
			
		}
		
	}
	
	if(n!=1){
		
		vec.push_back({n,1});
	}
	
	auto it=vec.begin();
	for(it;it!=vec.end();it++){
		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