CDVNT01G-Editorial

PROBLEM LINK:

Practice

Contest: CodeVenture 1.0

Setter: Krunal Mathukiya

Tester: Malhar Patel

Editorialist: Nisarg Thakkar

DIFFICULTY:

Simple

PREREQUISITES:

Prime Factorization, Sieve of eratosthenes

PROBLEM:

The idea behind the problem boils down to following : You are given number N and you need to find the sum of all the prime factors of the given Number.

EXPLANATION

For example let’s take N=45 then its Prime Factorization is 3 X 3 X 5.
Hence answer will be sum of that i.e. 11

TIME COMPLEXITY

Time complexity is O(NloglogN).

SOLUTIONS:

CPP Solution

#include <bits/stdc++.h>

using namespace std;
#define ll long long int
#define pb push_back
#define llu unsigned long long int
#define fo(i,n) for(int i=0;i<n;i++)
#define eb emplace_back
#define M 1000000007
#define vi vector
#define vlli vector
#define pi pair<int,int>
#define mp make_pair
#define mapi map<int,int>
ll max(ll x,ll y)
{
if(x>y)
return x;
return y;
}
ll min(ll x,ll y)
{
if(x<y)
return x;
return y;
}
void yes()
{
cout << “YES” << endl;
}
void no()
{
cout << “NO” << endl;
}
int primeFactors(int n)
{
ll sum=0;
sum=0;
if(n%2==0) sum=2;
while(n%2==0) n /= 2;
for(ll i=3;i*i<=n;i+=2)
{
if(n%i==0) sum += i;
while(n%i==0) n/=i;
}
if(n>1) sum+=n;
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//cin.ignore(numeric_limits::max(),’\n’);
//const unsigned int M=1000000007;
ll test;
cin >> test;
//test=1;
while(test–)
{
ll m;
cin >> m;
cout << primeFactors(m) << endl;
}
return 0;
}

Feel free to Share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile: