#CF26A. 几乎是质数

几乎是质数

CF26A Almost Prime

题目描述

\hspace{15pt}如果一个数恰好有两个不同的质因子,那么它被称为几乎是质数的数。例如,6,18,246,18,24 就是几乎是质数的数,而 4,8,9,424,8,9,42 不是。

\hspace{15pt}请你求出 11 到 nn 中几乎是质数的数有多少个。

输入格式

\hspace{15pt}在一行上输入一个整数 n(1≦n≦3×103)n \left(1 \leqq n \leqq 3 \times 10^3 \right),代表需要统计的上界。

输出格式

\hspace{15pt}在一行上输出一个整数,代表 11 到 nn 中几乎是质数的数的数量。

测试样例

10

2

21

8