AcWing4622-整数拆分

📌题目

题目：4622.整数拆分

我们规定 $f(x)$ （x≥2）表示整数 x 的除本身之外的最大因数。

例如， $f(6)=3$ ， $f(25)=5$ ， $f(2)=1$

现在，给定一个整数 n，请你将其拆分为 k 份 $n_1,n_2,...,n_k$ （也可以不拆分，即 k=1），要求：

$n_1+n_2+...+n_k=n$
对于 $1≤i≤k$ ， $n_i≥2$ 始终成立。
$f(n_1)+f(n_2)+…+f(n_k)$ 的值应尽可能小。

输出 $f(n_1)+f(n_2)+…+f(n_k)$ 的最小可能值。

输入格式

一个整数 n

输出格式

一个整数，表示 $f(n_1)+f(n_2)+…+f(n_k)$ 的最小可能值。

数据范围

前 4 个测试点满足 $2≤n≤30$ 。
所有测试点满足 $2≤n≤2×10^9$

示例1

输入：4

输出：2

示例2

输入：27

输出：3

🔎题解

f(x)表示整数 x 的除本身之外的最大因数，那么当x为质数时，f(x)=1，所以这一题其实就是让我们用最少的质数相加得到x，质数的个数就是这一题的答案。

那么当x为质数时，f(x)直接就等于1了，不用拆分。
当x为偶数时，这里就要讲一个非常著名的猜想：哥德巴赫猜想。哥德巴赫猜想是说，对于任意一个大于2的偶数都可以拆分成两个质数之和（虽然只是猜想，没法验证，但是用起来是完全没问题的）。所以当x为偶数时，结果就是2。
当x为奇数时，我们要再分情况考虑：
- 如果x-2是一个质数，那么我们把x拆分成x-2和2就可以得到最小的结果，结果是2；
- 如果x-2不是质数，我们就可以把x拆分成3和一个偶数，这样的结果是3。

分析源自->

作者：你好A
链接：https://www.acwing.com/solution/content/140215/

代码如下：

#include <cstdio>
#include <cmath>

using namespace std;

// 判断是否是质数
bool isPrime(int n){
    for(int i=2; i<=n/i; i++){
        if(n%i==0) return false;
    }
    return true;
}

int main(){
    
    int n;
    scanf("%d", &n);
    if(isPrime(n)) printf("%d", 1);  // 如果是质数，不拆，结果是1
    else if(n%2 == 0) printf("%d", 2);  // 如果是偶数，可以拆成2个质数（哥德巴赫猜想），结果是2
    else{
        // 如果是奇数，看n-2是不是质数，是则拆成 (n-2)+2，否则拆成 3 + 一个偶数，结果是3
        if(isPrime(n-2)) printf("%d", 2);
        else{
            printf("%d", 3);
        }
    }
    
    
    return 0;
}