[CF735D]Taxes

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题 目大意： 给你$n$，把它分成若干个数$n_i$，记价值为$\sum_{i=1}^k(\sum_{j|n_i}j-n_i)$（即分成的每个数的约数和（不包括自身））。（以前写的题，不知道为什么没交）

题解： 分成质数，根据哥德巴赫猜想，大于$2$的偶数都可以分成两个质数的和，那么奇数有$3$中可能：$1.$自己是质数；$2.$分成$2$和一个质数；$3.$分成一个质数和一个偶数（再分成两个质数）

卡点： 无

C++ Code：

#include <cstdio>

#include <cstdlib>

#include <cmath>

inline bool check(int x) {

	int t = sqrt(x);

	for (int i = 2; i <= t; i++) if (x % i == 0) return false;

	return true;

}

inline void Halt(int x) {

	printf("%d\n", x);

	exit(0);

}

int n;

int main() {

	scanf("%d", &n);

	if (check(n)) Halt(1);

	if (n & 1) {

		if (check(n - 2)) Halt(2);

		else Halt(3);

	} else Halt(2);

	return 0;

}