筛选法求素数

题号：NC22099
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 使用下方所描述的筛选法，求解 $n$ 以内的全部素数，同时输出被置为 $0$ 的整数个数。

$\hspace{15pt}$ 筛选法求解的过程为：
${\hspace{20pt}}_\texttt{1.}\,$ 将 $2$ 到 $n$ 之间的整数放在数组内存储；
${\hspace{20pt}}_\texttt{2.}\,$ 将数组中 $2$ 之后的所有能被 $2$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{3.}\,$ 将数组中 $3$ 之后的所有能被 $3$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{4.}\,$ ……；以此类推，直到将数组中 $n$ 之后的所有数都置为 $0$ 为止；
${\hspace{20pt}}_\texttt{5.}\,$ 此时，数组中剩余的非 $0$ 的数即为 $n$ 以内的全部素数。

【名词解释】
$\hspace{15pt}$ 素数：也称质数。一个大于 $1$ 的正整数，如果除了 $1$ 和它自身以外不再有其他因数，那么这个数被称作素数。特殊地， $1$ 既不是素数也不是合数。

输入描述:

在一行上输入一个整数 。

输出描述:

第一行输出若干个整数，表示  以内的全部素数，用空格分隔。
第二行输出一个整数，表示被置为  的整数个数。

示例1

输入

复制

输出

复制

2 3 5 7 11 13 17 19
11