object Main {
  def main(args: Array[String]): Unit = {
    io.Source.stdin.getLines foreach (n => println(pi(n.toInt)))
  }
  val primes: IndexedSeq[Int] = prime_sieve(50000)
  def prime_sieve(x: Int): IndexedSeq[Int] = {
    val n = x - x % 6 + 6
    val correction = if (x % 6 > 1) 1 else 2
    val sieve = Array.fill(n/3)(true)
    for (i <- 1 to (Math.sqrt(n) / 3).toInt if sieve(i)) {
      val k = (3 * i + 1) | 1
      for (j <- (k * k) / 3 until sieve.length by 2*k) sieve(j) = false
      for (j <- (k*(k-2*(i&1)+4))/3 until sieve.length by 2*k) sieve(j) = false
    }
    2 +: 3 +: (for (i <- 1 until n / 3 - correction if sieve(i)) yield (3*i+1)|1)
  }
  def bisect(n: Int): Int = {
    def loop(left: Int, right: Int): Int = {
      val mid = (left + right) / 2
      if (primes(mid) <= n && n < primes(mid+1)) mid+1
      else if (n < primes(mid)) loop(left, mid)
      else loop(mid+1, right)
    }
    if (n < primes.head) 0
    else if (n >= primes.last) primes.length
    else loop(0, primes.length)
  }
  def pi: Memoized[Int, Int] = Memoized {x =>
    if (x <= primes.last) bisect(x)
    else {
      val a = pi(Math.sqrt(Math.sqrt(x)).toInt)
      val b = pi(Math.sqrt(x).toInt)
      val c = pi(Math.cbrt(x).toInt)

      var result = phi(x, a) + ((b + a - 2) * (b - a + 1)) / 2
      for (i <- a + 1 to b) {
        val w = x / primes(i - 1)
        val b_i = pi(Math.sqrt(w).toInt)
        result -= pi(w)
        if (i <= c)
          for (j <- i to b_i)
            result = result - pi(w / primes(j - 1)) + j - 1
      }
      result
    }
  }
  def phi: Memoized[(Int,Int), Int] = Memoized {
    case (x, a) =>
      if (a == 1) (x + 1) / 2
      else phi(x, a - 1) - phi(x / primes(a - 1), a - 1)
  }
  case class Memoized[Arg, Ret](f: Arg => Ret) extends (Arg => Ret) {
    val cache = collection.mutable.Map[Arg, Ret]()
    def apply(arg: Arg) = cache.getOrElseUpdate(arg, f(arg))
  }
}