codeIQ 1621

なんとなくlower_boundでやりたかった.

vector<ll> p;

void init()
{
  p.resize(10000);
  fill(p.begin(),p.end(),1LL<<30);
  int m = 0; p[m++] = 2;
  for(int i=3;i<=100000;i+=2)
  {
    bool flag = true;
    for(int j=0;p[j]*p[j]<=i;j++)
    {
      if(i%p[j]==0)
      {
        flag = false;
        break;
      }
    }
    if(flag) p[m++] = i;
  }
}

void solve()
{
  init();
  int d;
  while(cin >> d)
  {
    int ans = lower_bound(p.begin(),p.end(),d)-p.begin();
    printf("%d\n",ans);
  }
}

int main()
{
  solve();
  return 0;
}