ciuru lu Erastotene

#include <bits/stdc++.h>
using namespace std;
bool prime[50000000];

int main()
{
 memset(prime,true,sizeof(prime));
 int n,nr=0,i,j;
 cin>>n;
 for (i=2;i*i<=n;i++)
  if (prime[i])
  {
     for (j=i*i;j<=n;j+=i)
      prime[j]=false;
  }
  for (i=2;i<=n;i++)
  if (prime[i])
    nr++;
  cout<<nr;
    return 0;
}