1=N

[题目链接](https://www.nowcoder.com/practice/31469f8503c24914acd5c0290ad4dfbb)

思路

先来理解题意。初始 $X = 1$ ，每次操作可以选一个 $K \geq 2$ ，花费 $K$ 的代价把 $X$ 变成 $K \times X$ 。目标是让 $X = N$ ，问最小总代价。

换句话说，我们要把 $N$ 写成若干个 $\geq 2$ 的整数的乘积 $N = K_1 \times K_2 \times \cdots \times K_t$ ，使得 $K_1 + K_2 + \cdots + K_t$ 最小。

那什么样的分解方式代价最小呢？

假如某个 $K_i$ 是合数，比如 $K_i = a \times b$ （ $a, b \geq 2$ ），那把它拆成两步 $a$ 和 $b$ ，代价从 $a \times b$ 变成 $a + b$ 。由于 $a, b \geq 2$ ，显然 $a + b \leq a \times b$ （等号在 $a = b = 2$ 时成立）。所以把合数拆开，代价不会变大。

这就意味着：最优方案一定是把 $N$ 分解成质因数的乘积，每一步选一个质因子作为 $K$ 。最终答案就是 $N$ 的所有质因数之和（含重复）。

拿样例验证一下： $N = 12 = 2 \times 2 \times 3$ ，代价 $= 2 + 2 + 3 = 7$ ，正确。

特别地， $N = 1$ 时不需要任何操作，代价为 $0$ 。

做质因数分解只需要从 $2$ 开始试除，每次能整除就累加该因子并除掉，直到 $p^2 > N$ 。如果最后剩余的 $N > 1$ ，说明它本身是一个质因子，也要加上。

代码

C++
Java
Python3
JavaScript

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int cost = 0;
    for(int p = 2; p * p <= n; p++){
        while(n % p == 0){
            cost += p;
            n /= p;
        }
    }
    if(n > 1) cost += n;
    cout << cost << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cost = 0;
        for (int p = 2; p * p <= n; p++) {
            while (n % p == 0) {
                cost += p;
                n /= p;
            }
        }
        if (n > 1) cost += n;
        System.out.println(cost);
    }
}

n = int(input())
cost = 0
p = 2
while p * p <= n:
    while n % p == 0:
        cost += p
        n //= p
    p += 1
if n > 1:
    cost += n
print(cost)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    let n = parseInt(line.trim());
    let cost = 0;
    for (let p = 2; p * p <= n; p++) {
        while (n % p === 0) {
            cost += p;
            n = Math.floor(n / p);
        }
    }
    if (n > 1) cost += n;
    console.log(cost);
    rl.close();
});

复杂度分析

时间复杂度: $O(\sqrt{N})$ 。试除法最多枚举到 $\sqrt{N}$ ，内层 while 循环的总次数不超过 $\log N$ 。
空间复杂度: $O(1)$ 。只用了常数个变量。