质数又称素数。指在一个大于 $1$ 的自然数中，除了 $1$ 和此整数自身外，不能被其他自然数整除的数。
素数在数论中有着很重要的地位。比1大但不是素数的数称为合数。$1$ 和 $0$ 既非素数也非合数。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题，如哥德巴赫猜想等。算术基本定理证明每个大于 $1$ 的正整数都可以写成素数的乘积，并且这种乘积的形式是唯一的。这个定理的重要一点是，将 $1$ 排斥在素数集合以外。如果 $1$ 被认为是素数，那么这些严格的阐述就不得不加上一些限制条件。
概念：只有 $1$ 和它本身两个约数的自然数，叫质数（Prime Number）。如：由 $2÷1=2,\ 2÷2=1$，可知 $2$ 的约数只有 $1$ 和它本身 $2$ 这两个约数，所以 $2$ 就是质数。与之相对立的是合数：“除了 $1$ 和它本身两个约数外，还有其它约数的数，叫合数。如：$4÷1=4,\ 4÷2=2,\ 4÷4=1$，很显然，$4$ 的约数除了 $1$ 和它本身这两个约数以外，还有约数 $2$，所以 $4$ 是合数。）
$100$ 以内的质数有 $2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47,\ 53,\ 59,\ 61,\ 67,\ 71,\ 73,\ 79,\ 83,\ 89,\ 97$，共有 $25$ 个质数。
注：
（1）$1$ 既不是质数也不是合数。因为它的约数有且只有 $1$ 这一个约数。
（2）$2$ 和 $3$ 是所有素数中唯一两个连着的数。

第一行输入一个正整数 n， $2 \leq n \leq 30,000$。