➤ Problem Link : APS
👉 Hint : Precompute smallest prime factors for all numbers
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll par[10000010];
void findPrimes(ll n)
{
for(ll i=1;i<=n;i++)
par[i]=i;
for(ll i=2;i*i<=n;i++)
{
if(par[i]==i)
{
for(ll j=i*i;j<=n;j+=i)
{
if(par[j]==j)
par[j]=i;
}
}
}
}
int main()
{
findPrimes(10000000);
int t;
cin>>t;
par[1]=0;
for(ll i=2;i<=10000000;i++)
{
par[i]+=par[i-1];
}
while(t--)
{
ll n;
cin>>n;
cout<<par[n]<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.