26A. Almost Prime - Codeforces Solution C++

➤  Problem Link : 26A. Almost Prime 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int arr[n+1];
	int i,j;
	for(i=0;i<=n;i++)
		arr[i]=i;
	for(i=2;i*i<=n;i++)
	{
		if(arr[i]==i)
		{
			for(j=i*i;j<=n;j+=i)
			{
				if(arr[j]==j)
					arr[j]=i;
				
			}
		}
	}
	int cnt=0;
	for(i=1;i<=n;i++)
	{
		set<int>s;
		int j=i;
		while(j!=1)
		{
			s.insert(arr[j]);
			j/=arr[j];
		}
		if(s.size()==2)
			cnt++;
	}
	
	cout<<cnt;
	return 0;
}

 

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!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

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.