# 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
#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