tax
题目：
小码哥要交税，交的税钱是收入 \(n\) 的最大因子（该最大因子为不等于 \(n\) 的最大因子），但是现在小码哥为了避税，把钱拆成几份（每份至少为 \(2\)），使交税最少，输出税钱。
格式：
输入格式：一个正整数 \(n\) 表示所以的钱数。
输出格式：输出一个正整数，表示税钱。
样例：
输入：4
输出：2
备注：
对于 \(30\%\) 的分数，\(2 \le n \le 100\)；
对于 \(50\%\) 的分数，\(2 \le n \le 10000\)；
对于 \(100\%\) 的分数，\(2 \le n \le 2 \times 10^9\)。
思路：
- 如果 \(n\) 为质数，则不等于 \(n\) 的最大因子为 \(1\)；
- 如果 \(n\) 为偶数，由强哥德巴赫猜想（任何一个大于 \(2\) 的偶数都可以表示成两个素数之和）知，\(n\) = 质数+质数，此时交税最少，应输出 \(2\)。
- 如果 \(n\) 为奇数，奇数 = 奇数+偶数，我们尽可能将 \(n\) 拆成一个质数和一个偶数，因为除 \(2\) 以外所有质数均为奇数，此时交税最少，应输出 \(3\)。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
bool prime(int num) {
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
cin >> n;
if (prime(n)) {
cout << 1;
} else if (n % 2 == 0) {
cout << 2;
} else if (prime(n-2)) {
cout << 2;
} else {
cout << 3;
}
return 0;
}
约数个数
题目：
给定正整数 \(n\)，求 \(n\) 的约数个数。
格式：
输入格式：一个正整数 \(n\)。
输出格式：输出一行一个整数表示答案。
样例：
输入：12
输出：6
备注：
\(1 \le n \le 10^9\)
思路：
-
直接枚举从 \(1\) 到 \(\sqrt n\) 的所有数
-
有求约公式如下：
若 \(n=\prod_{i=1}^{k}p_i^{a_i}=p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}\) ，其中 \(p_i\) 为质数，\(a_{i}\) 为正整数，则 \(n\) 的正约数个数为 \(f(n)=\prod_{i=1}^k(a_i+1)=(a_1+1) \times (a_2+1) \times ... \times (a_k+1)\)
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int main() {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i * i <= n; i++) {
if (n%i == 0) {
ans += 2; // 加两个数，一个是i，另一个是n/i
}
if (i*i == n) {
ans--; // 特判i*i=n
}
}
cout << ans;
return 0;
}