梅森合数

问题描述

全球协作计算任务之一是“伟大的互联网梅森素数搜索”（GIMPS），旨在通过研究特定类别的素数来寻找更大的素数。

梅森数被定义为形如$(2^p - 1)$的数，其中$p$是素数（即只能被1和自身整除的数）。如果一个数能被其他数整除，则称为合数，并且每个合数可以唯一地表示为多个素数的乘积（这些素数称为它的质因数）。

最初，梅森数似乎都是素数：

但显然，如果需要进行“伟大的互联网”搜索，说明并非所有梅森数都是素数。

给定输入参数$k$，计算所有小于$2^k$的梅森合数（即梅森数为合数的情况），其中$k \leq 63$（确保结果可用64位有符号整数存储）。例如，在C++中，long long是64位有符号整数。

输入

输入为一个整数$k$（无前导或尾随空格），满足$k \leq 63$。

输出

每行输出一个梅森合数的质因数分解，格式如下：
质因数1 * 质因数2 * ... = 梅森数 = ( 2 ^ p ) - 1
其中，质因数按升序排列，严格遵循示例格式（空格和符号位置需完全一致）。

示例输入

31

示例输出

23 * 89 = 2047 = ( 2 ^ 11 ) - 1  
47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1 
233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1  

来源

Pacific Northwest 2004