/*
Codul sursa arata putin urat pentru ca nu lucram direct cu i ci cu 2*i+1,
am mai facut optimizarea ce apare si in mathworld, nu parcurgem numerele
pana la n pentru marcarea multiplilor ci pana la sqrt(n) lucru care
e evident dupa cele explicate mai sus.
Ultima imbunatatire care o vom aduce este aceea de a folosi mai putina memorie.
 Cum pentru fiecare numar e necesara doar o informatie booleana, aceasta o putem
 tine intr-un bit, nu este necesar un char intreg. Sa vedem cum arata codul:

 Documentare pe >>, << , |, & is operati pe biti
            observatie:
                   - daca e i<<1 il inmulteste pe i cu 2
                   - daca e 1<<i il ridica pe 2 la puterea lui i
                   - daca e 2<<i face 2*2^i
*/


  const int MAXSIZE = 100000000/2/8+1;    //imparte la 2 pt ca se exclud nr. pare
                                   // se imparte la 8 pt. ca char e pe 8 biti
                                   //e +1 pt.ca se aloca o poz. si pt. un caracter de siguranta

#include <fstream>
using namespace std;

//class PrimeNumbersSieve1

  char p[MAXSIZE] ;  int n;
  //p[i] == 0 if i is prime
  int ciur(int n)
  {
    int i, j, nr;

    nr=1;

                  /* ((i * i) << 1)       il imparte la 2 */
    for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1)        /*se calculeaza poz. pe biti*/
    {
      /*p[i >> 3]       valoarea lui i o imparte cu 2^3 */
      /*1 << (i & 7)    face i & 7 pe biti care e 111   */
      if ((p[i >> 3] & (1 << (i & 7))) == 0)
      {
        for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1)
        {
           /* p[j >> 3] muta biti in dreapta cu 3 pozitii  */
           /* "|"  sau pe biti                             */
          p[j >> 3] = p[j >> 3] | (1 << (j & 7));
        }
      }
    }


    //(p[i>>3]&(1<<(i&7))) == 0 if 2*i + 1 is prime
    for (i = 1; 2 * i + 1 <= n; ++i)

    /* p[i >> 3]         gasirea charului                       */
    /* (1 << (i & 7))    gasirea bitului din cadrul unui char   */
         if ((p[i >> 3] & (1 << (i & 7))) == 0)
             nr++;





    return nr;
  }


int main()
{
    ifstream f("ciur.in");
    ofstream g("ciur.out");
    f>>n;
    g<<ciur(n);

    g.close();
    f.close();
    return 0;
}