私は現在力ずくで解決している最適化問題を抱えていますが、もっと良い方法があることを願っています。
問題: と が与えられnたdとき、p1^e1, ..., pk^ekpi
p1^e1 * ... * pk^ek >= n^dp1^e1 + ... + pk^ek < n最小限です私の現在の解決策は、可能なすべての素数のサブセット (最大で固定数まで) を反復処理し、次に可能なすべての指数 (最大で固定数まで) を反復処理してから、条件 1 をテストし、合計がこれまでで最小かどうかを確認することです。これには非常に長い時間がかかります。これをスピードアップするために私ができるもっと賢いことはありますか?
これはナップサック問題のようです。NP完全だと思います。実際、（d = 1）の場合、最適化は因数分解と同等である可能性があります。
ただし、すべてのナップサック問題がNP困難であるわけではありません。これが、Merkle-Hellmanナップサック暗号システムが壊れた理由です。
AM-GM 不等式とその他の制約を使用すると、次のことが得られます。
(n / k)^k > 製品 >= n^d
したがって、n^(kd) > k^k です。log を基数 n にすると、kd > k*log(k) が得られます。k <= n (合計に基づく) k * (1 - log(k)) > d なので
上記の LHS をプロットして、k の推定値を得ることができます。