最大乘积

题目描述

一个正整数可以表示为若干个互不相同的正整数之和，如 '6=1+5=2+4=1+2+3=6'，有 '4' 种表示方法，这 '4' 种表示方法里，拆分出的数字的乘积分别为 '5'、'8'、'6'、'6'。 给出 'n'，求 'n' 的所有表示方案中，拆分出的数字的乘积最大的方案，按升序依次输出拆分出的数字。

输入格式

从标准输入读入数据。 输入一个正整数 'n'（'n≤10^6'）。

输出格式

输出到标准输出。 按升序输出拆分出的数字。

样例 #1

样例输入 #1

6

样例输出 #1

2 4

样例 #2

样例输入 #2

100

样例输出 #2

2 3 5 6 7 8 9 10 11 12 13 14

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n;
int p[N], cnt;
bool st[N];
struct Node
{
    int x, y;
    bool operator < (const Node &t) const
    {
        return x < t.x || x == t.x && y < t.y;
    }
}res;

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) p[cnt ++ ] = i;
        for (int j = 0; p[j] <= n / i; j ++ )
        {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }

    for (int i = 0; i < cnt && p[i] <= n / p[i]; i ++ )
    {
        int k = n;
        for (int j = i; j < cnt && p[j] <= k / p[i]; j ++ )
        {
            k /= p[j];
            if (k % p[i]) continue;
            int t = 0;
            while (k % p[i] == 0) k /= p[i], t ++ ;
            if (t > res.y) res = {p[i], t};
        }
    }

    if (res.x) cout << res.x << ' ';
    for (int i = 0; i < cnt && p[i] <= n / res.x; i ++ )
        if (p[i] != res.x) cout << p[i] << ' ';

    return 0;
}