 # Prime Issue | PRIMEISSUE

Prime Issue

Setter: Ayush Kumar
Tester: Ramandeep Singh
Editorialist: Ayush Kumar

Easy

# problem

Chirag has two sons Ritik and Ankit , both of them were fighting with each other. Later on Chirag came and asked both his son to stop fighting and perform a task. He asked them both to pick a number and calculate the summation of frequency of prime factors of the number they picked. Your task is to help those kids find the solution of the task assigned.

# Explanation

In this question, we have to observed that for any number N we can find their all primes factor up to

O(sqrt(n) x log(n))

let our number is n
Nive approach :

• initialize count = 0

• While n is divisible by 2, divide n by and continuously increment count until it became an odd number.

• After step 1, n must be odd. Now start a loop from i = 3 to the square root of n. While i divides n,divide n by i.
After i fails to divide n, continuously increment count, increment i by 2 and continue.

• If n is greater than 2 then it must be a prime number so increment count by 1.

now count is the ans for 1 son for other son do similar process

# Time Complexity

O(sqrt(n) x log(n))

# solution

``````#include<bits/stdc++.h>
using namespace std;
#define int long long int
int fun(int n)
{
unordered_map<int,int>mp;
int ct =0;
if(n%2==0)
{
while(n%2==0)
{
n/=2;
ct++;
}
mp = ct;
}

for(int i=3;(i*i)<=n;i+=2)
{
if(n%i==0)
{
ct=0;
while(n%i==0)
{
ct++;
n/=i;
}
mp[i] = ct;
}
}

if(n>2)
{
mp[n] = 1;
}
int sum = 0;
for( auto ele:mp)
{
sum+=ele.second;
}
return sum;
}

void solve()
{
int n1,n2;
cin>>n1>>n2;

int ans1 = fun(n1);
int ans2  = fun(n2);

cout<<ans1<<" "<<ans2;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
solve();
return 0;
}
``````