$prime = {}
$pas = {}
$pas[2] = 1
$pas[3] = 2
def prime_array_size(max)
  if max < 2
    ans = 0
  else
    max -= 1 if max % 2 == 0
    while max > 3
      break if is_prime(max)
      max -= 2
    end
    unless $pas[max]
      i, ans = $pas.sort[-1]
      while i <= max
        if is_prime(i) then
          $pas[i] = ans
          ans += 1
        end
        i += 2
      end
    end
    return $pas[max]
  end
end

def is_prime(n)
  unless $prime[n]
    if n < 2
      $prime[n] = false
    elsif n < 4
      $prime[n] = true
    elsif n % 2 == 0
      $prime[n] = false
    else
      i = 3
      flag = true
      while i <= Math.sqrt(n)
        if n % i == 0 then
          flag = false
          break
        end
        i += 2
      end
      $prime[n] = flag
    end
  end
  return $prime[n]
end

while n = gets
  puts prime_array_size(n.to_i)
end