CF-735D Taxes 题解

题目大意

给你一个数，对于这个数n你需要付出的代价是自身的最大的非本身因子$（n\ge 2)$，你可以将这个数拆成任何多的整数，求所需的最小代价。

解题思路

这题需要用到哥德巴赫猜想。

哥德巴赫猜想：任意一个大于4的偶数，都可以分解为两个奇质数的和。

首先判断是不是质数，是质数就输出1。

之后判断是不是偶数，是偶数就输出2。

如果还不是偶数的话，就可以把这个数拆成2+（n-2），还需要判断这个（n-2）是不是质数，如果是答案为2，否则答案为4。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6 + 5;
int prime[N], cnt;
bool vis[N];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans *= a;
		a <<= 1, b >>= 1;
	}
	return ans;
}

int check(int n) {
	rep(i, 2, sqrt(n)) {
		if (n % i==0)	return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n; cin >> n;
	if (check(n))	cout << 1 << endl;
	else if ((n&1)==0) cout << 2 << endl;
	else {
		if (check(n - 2))	cout << 2 << endl;
		else cout << 3 << endl;
	}
	return 0;
}