T. 素数筛选(Hard)（7.27）

素数（质数）是指大于 $1$ 的自然数中，除了 $1$ 和它本身外没有其他正因数的数。
给定一个正整数 $n$，请输出区间 $[2,n]$ 内的所有素数。

注意反常的时间限制

一行一个正整数 $n$。

第一行输出 The Prime Numbers between 1 and n are:，其中 n 替换为输入的数值。

接下来，每行输出 $10$ 个素数，每个素数占用 $8$ 个字符宽度，每个素数占 $8$ 个字符宽度输出后，再输出一个空格（见提示）。

最后一行输出 Total of k prime numbers between 1 and n.，其中 k 替换为素数的个数。

输入 1

8

输出 1

The Prime Numbers between 1 and 8 are:
       2        3        5        7
Total of 4 prime numbers between 1 and 8.

输入 2

50

输出 2

The Prime Numbers between 1 and 50 are:
       2        3        5        7       11       13       17       19       23       29
      31       37       41       43       47
Total of 15 prime numbers between 1 and 50.

数据范围

提示

• C++ 中可以用 cout << setw(8) << P[i] << ' '; 来设置输出宽度为 $8$ 并留空格，右对齐。
• 【medium】试除法判断时，需要判断到 $[2, n-1]$ 中的每一个数吗？
• 【hard】约数和倍数的关系是什么？