Codeforces Round #382 (Div. 2) D. Taxes 数论、哥德巴赫猜想

My Solution

题意：给定一个数n，n可以分成k个数的和(ni >= 2 , sum{ni} == n, k 可以为 1)，花费为ni的除本身外的最大因数，求花费和的最小值。

数论、哥德巴赫猜想

然后2是素数所以ans = 1；

当n 为 奇数时判断是否为素数，如果是素数则 ans = 1；

如果不是，则判断 n - 2是否为素数，如果是则可以把n拆成一个素数和2 ans = 2；

否则只能拆成一个素数+一个大于2的偶数 ans = 3；

复杂度 O(sqrt(n))

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

inline bool isprime(int n)
{
    if(n <= 1) return false;
    int m = floor(sqrt(n) + 0.5);
    for(int i = 2; i <= m; i++){ if(n % i == 0) return false; } return true; } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 9; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n; cin >> n;
    if(n == 2) cout << 1 << endl;
    else if(n == 3) cout << 1 << endl;
    else if(n == 4) cout << 2 << endl;
    else if(n == 5) cout << 1 << endl;
    else{
        if(n % 2 == 0) cout << 2 << endl;
        else{
            if(isprime(n)) cout << 1 << endl;
            else if(isprime(n - 2)) cout << 2 << endl;
            else cout << 3 << endl;
        }
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx