➤ Problem Link : DIV
👉 Hint : Use Sieve method to find smallest prime factor
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int minPrime[1000001];
int cnt[1000001];
void seive()
{
int n=1000000;
cnt[1]=1;
for(int i=2;i<=n;i++)
cnt[i]=2; // 1 && itself
minPrime[1]=0;
for(int i=2;i<=n;i++)
{
minPrime[i]=i;
for(int j=2*i;j<=n;j+=i)
cnt[j]++;
}
for(int i=2;i*i<=n;i++)
{
if(minPrime[i]!=i)
continue;
for(int j=i*i;j<=n;j+=i)
if(minPrime[j]==j)
minPrime[j]=i;
}
}
int main()
{
int n=1000000;
seive();
int c=9;
for(int i=2;i<=n;i++)
{
int l=cnt[i];
// cout<<i<<" "<<l<<endl;
int x=minPrime[l];
int y=l/x;
if(x!=y && minPrime[y]==y)
{
// cout<<i<<"\n";
c--;
if(c==0)
{
cout<<i<<"\n";
c=9;
}
}
}
}
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.