首页 > 试题广场 >

1=N

[编程题]1=N

热度指数：1792 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正整数 ${X}$ ,令 ${X = 1}$ :
你可以对整数 ${X}$ 执行以下操作(次数不限):
选择一个大于等于 ${2}$ 的整数 ${K}$ 。支付 ${K}$ 单位的成本，令 ${X = K \times X}$ 。
给定正整数 ${N}$ ，找出使 ${X = N}$ 所需的最小成本

输入描述:

输入的第一行包含一个正整数。

输出描述:

输出使所需的最小成本

示例1

输入

输出

算法知识视频讲解

Java

BraveCoder

核心思路：将 N 分解为质因数的乘积，最小成本就是所有质因数（包括重复的）之和。

原因：当 a, b>=2 时，a+b<=a*b 恒成立，因此分解为质因数的成本最低。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.close();

        System.out.println(minCost(N));
    }

    private static int minCost(int n) {
        if (n == 1) return 0;

        int cost = 0;

        // 分解质因数
        for (int i = 2; i * i <= n; i++) {
            // 计算质因数i的指数
            while (n % i == 0) {
                cost += i;  // 累加质因数作为成本
                n /= i;
            }
        }

        // 如果剩余的n是一个质数
        if (n > 1) {
            cost += n;
        }

        return cost;
    }
}

发表于 2025-09-06 17:49:13 回复(0)

精致的熊熊在努力存钱

def func(x):

if x <= 3:

return x

for i in range(2,int(x**0.5)+1):

if x%i == 0:

return i

else:

return x

def is_jhzs(x:int):

li = []

while True:

curr = func(x)

if curr == x:

li.append(curr)

break

x = int(x/curr)

li.append(curr)

return sum(li)

N = int(input())

print(is_jhzs(N))

发表于 2025-10-04 17:34:23 回复(0)

C++

爱吃香菜的雪碧也不容易

#include <iostream>

using namespace std;

int main() {

int a;

int tep = 0;

cin >> a;

if (a == 1) return 1;

for (int i = 2; i <= a; i++){

if (a % i == 0) {

tep += i;

a /= i;

i = 1;

}

if (a == 1){

break;

}

cout << tep << endl;

}

发表于 2025-06-04 20:07:33 回复(0)

Java

一个普通求职者

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int cost = 0;
        for (int i = 2; n != 1; i++) {
            while (n != 1 && n % i == 0) {
                cost += i;
                n /= i;
            }
        }
        System.out.println(cost);
    }
}

发表于 2025-04-07 20:29:22 回复(0)

wjm_lzy

#include <iostream>
using namespace std;

int minCost(int N) {
    if (N == 1) return 0;
    int cost = 0;
    for (int p = 2; p * p <= N; ++p) {
        if (N % p == 0) {
            int e = 0;
            while (N % p == 0) {
                e++;
                N /= p;
            }
            cost += p * e;
        }
    }
    if (N > 1) cost += N; // 剩余未分解的大于1的质数
    return cost;
}

int main() {
    int N;
    cin >> N;
    cout << minCost(N) << endl;
    return 0;
}

发表于 2025-04-01 23:41:17 回复(0)

一笑而过2222

N = int(input("请输入正整数N: ")) x = 1 cost = 0 while x < N: k = 2 while k * x <= N: if (N % (k * x) == 0): cost += k x *= k break k += 1 print(cost)

发表于 2025-03-18 11:39:18 回复(1)

提交观点

问题信息

贪心数论

上传者：turnsoul

难度：

6条回答 7收藏 276浏览

1=N

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题