# エラトステネスの篩いによる素数列の生成
def eratosthenes(n)
  return [] unless n.is_a?(Integer) && n >= 2
  list = Array.new(n - 1).map.with_index {|i, k| k + 2}
  result = [1]
  while list.size >= 1 && list.last >= result.last**2
    p = list.shift
    result << p
    #list.delete_if {|v| v % p == 0 }
    #下の2行は上記一行に置換可能だが、上記では1/12の性能しか出ない。
    list.each.with_index(0) {|i, k| list[k] = nil if i % p == 0}
    list.compact!
  end
  result.shift
  result = result + list
  result.sort_by! {|v| v}
end

def bsearch2(ary, key, l, h)
  return nil if ary == [] 
  return nil if l > h
  return nil if l == h
  return nil if l < 0 || h >= ary.size
  return nil if key < ary[l] || ary[h] < key
  
  mid = ((h + l) / 2 + 1).truncate
  
  return ary[mid] if ary[mid] == key
  return ary[l] if l == h
  if key < ary[mid]
    bsearch2(ary, key, l, mid - 1)
  else
    bsearch2(ary, key, mid, h)
  end
end

list = eratosthenes(999999)
h = list.size

while line = gets
  n = line.chomp.to_i
  if n <= 1
    puts 0
    next
  end
  puts bsearch2(list, n, 0, h - 1) + 1
end