GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A21225. $充电宝$

填空题较易

知识点

数论因子分解贪心算法

题目描述

充电宝 题目描述 有一块电量为n的充电宝，她计划给若干块电池充电，每次充电时会有一定电量的损失，使用电量ai时，其损失电量为f(ai)，f(x)表示除x以外最大因子。注意：若只充电1点，其损失电量也为1。 应该如何分配用光电量，使得损失总量最小。 输入格式 输入一个正数表示总电量n 输出格式 输出最小损失电量 输入样例#1 4 输出样例#1 2 输入样例#2 9 输出样例#2 2 说明提示 2\leqn\leq2\times10 9

参考答案

#include<iostream>
int main(){
    int n;
    std::cin>>n;
    
    bool flag = true;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) flag = false;
    }
    if (flag) std::cout << 1;
    else if (n % 2 == 0) std::cout << 2;
    else std::cout << 3;
}

上一题下一题