CPRIME - Prime Number Theorem - SPOJ Solution C++

  Problem Link : CPRIME  


👉 Hint : edit please

 


✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

bool arr[100000001];
double cnt[100000001];

int main()
{
	ll n=100000000;
	for(ll i=2;i<=n;i++)
	    arr[i]=1;
	for(ll i=2;i*i<=n;i++)
	{
		if(arr[i]==0)
			continue;
		for(ll j=i*i;j<=n;j+=i)
			arr[j]=0;
	}

	cnt[2]=1;
	for(ll i=3;i<=n;i++)
		cnt[i]=cnt[i-1]+arr[i];
	while(1)
	{
		ll x;
		cin>>x;
		if(x==0)
			break;
		double f=cnt[x];
		double g=x/log(x);
		if(f>g)
			g=f-g;
		else
			g=g-f;

		g/=f;
		g*=100;
		cout<<fixed<<setprecision(1)<<g<<"\n";
	}

}

 

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