UOJ Logo LFYZ Online Judge

LFYZOJ

#102. 阶乘分解

统计

本题支持 hack。

问题描述

俗话说一个整数总能分解成许多个素数的积,也就是

$$p_1^{c_1} \times p_2^{c_2} \times \cdots \times p_k^{c_k}$$

其中 $p_i < p_j$ 当 $i < j$ 时。$p_i$ 为素数且 $c_i$ 不为 $0$。

现在,给你一个数 $n$,请你将 $n!$ 分解为如上的形式。

输入格式

一行一个整数 $n$。

输出格式

输出 $k$ 行,$k$ 是 $n!$ 的不同的质因子的个数。

第 $i$ 行是空白分开的两个整数 $p_i,c_i$。

请按照 $p_i$ 递增的顺序输出

样例一

input

6

output

2 4
3 2
5 1

explanation

$6!=1 \times 2 \times 3 \times 4 \times 5 \times 6=2^1 \times 3^1 \times 2^2 \times 5^1 \times (2^1 \times 3^1)=2^4 \times 3^2 \times 5^1$

数据范围与约定

对于 $100\%$ 的数据,$n \in [2,1000000]$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$