# 最大乘积## 题目描述一个正整数可以表示为若干个互不相同的正整数之和如 $6=1+5=2+4=1+2+3=6$有 $4$ 种表示方法这 $4$ 种表示方法里拆分出的数字的乘积分别为 $5$、$8$、$6$、$6$。给出 $n$求 $n$ 的所有表示方案中拆分出的数字的乘积最大的方案按升序依次输出拆分出的数字。## 输入格式从标准输入读入数据。输入一个正整数 $n$$nle10^6$。## 输出

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
int primes[N], cnt;
bool st[N];

void init()
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> n;

    init();

    int max_val = 1;
    int max_cnt = 0;
    for (int i = 0; primes[i] <= n; i ++ )
    {
        int x = primes[i];
        int res = n;
        int cnt = 0;
        while (res >= x) res -= x, cnt ++ ;
        if (cnt > max_cnt) max_cnt = cnt, max_val = x;
    }

    cout << max_val;
    int res = n - max_val;
    while (res)
    {
        for (int i = 0; primes[i] <= res; i ++ )
        {
            int x = primes[i];
            if (res >= x && res - x >= max_val - x)
            {
                cout << ' ' << x;
                res -= x;
                break;
            }
        }
    }
    cout << endl;

    return 0;
}
``