Prime Issue | PRIMEISSUE

Problem Link

Prime Issue

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

Difficulty

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[2] = 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;
}