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;
}