1=N

思路

题目在说什么？给你一个正整数 ，每次操作可以选择 的一个 的因子 ，将 变为 ，花费为 。问把 变成 的最小总花费。

关键观察

假设我们选了一个合数因子 （），一次操作花费 。但如果分两步：先除以 （花费 ），再除以 （花费 ），总花费 。

所以每次只除以质因数一定更优。

这意味着最小总花费就是 的所有质因数之和（含重复）。即对 ，答案为：

$$

以样例 为例：花费 。

实现

直接做质因数分解，枚举 到 的因子，累加每个质因子的贡献即可。时间复杂度 。

代码

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    for (long long p = 2; p * p <= n; p++) {
        while (n % p == 0) {
            ans += p;
            n /= p;
        }
    }
    if (n > 1) ans += n;
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

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

import math

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

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let n = BigInt(lines[0].trim());
    let ans = 0n;
    for (let p = 2n; p * p <= n; p++) {
        while (n % p === 0n) {
            ans += p;
            n /= p;
        }
    }
    if (n > 1n) ans += n;
    console.log(ans.toString());
});