计数质数

题目描述

给定一个整数 n，请你返回所有小于 n 的非负整数中，质数的数量。

质数是指大于 1 且除了 1 和其本身外没有其他正因数的整数。

输入格式

输入一行，包含一个整数 n。

输出格式

输出一个整数，表示所有小于 n 的质数个数。

数据范围

0 <= n <= 5 * 10^6

样例 1

输入

10

输出

4

说明

小于 10 的质数共有 4 个，它们是 2, 3, 5, 7。

样例 2

输入

0

输出

0

样例 3

输入

1

输出

0