Description

阿强愉快的拿到了自己工资，可是抠门的他发现自己还要没有交税。X国采用一种奇怪的税收方式。对于工资

num，需要收的税是p，p为num的最大的除数并且p不等于num。

（ps：6的最大除数是3，25的最大除数是5，2的最大除数是1）

为了减少人们要交的税，X国又规定可以把钱分开算税，分开的个数不限，即n1 + n2 + ... + nk = n，要交的

税就是每个部分的总和。

阿强现在向你寻求帮助，给定X最少要交多少钱的税？

Input

数据的组数 T；（T<=2000）

接下来T行，每行一个数字X（2 <= X <= 2e9）

Output

 对于每行X，输出最少的税Y

 

Sample Input

3
11
27
8

Sample Output

1
3
2

HINT

 

 对于第三个例子8，可以分为3+5，3和5的最大除数都是1，所以答案是2

C++版本一

题解：

任意一个大于2的偶数都能被拆分成两个素数的和。同时任意一个大于5的奇数都能被拆分成3个素数的和，一个为3，剩下的是偶数，按照前面的拆分即可。同时对于奇数还要考虑n-2为素数时，个数为2而不是3.

验证大素数则可以用米勒罗宾素数测试。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll mod_mul(ll a, ll b, ll n) {
    ll res = 0;
    while(b) {
        if(b&1)    res = (res + a) % n;
        a = (a + a) % n;
        b >>= 1;
    }
    return res;
}
ll mod_exp(ll a, ll b, ll n) {
    ll res = 1;
    while(b) {
        if(b&1)    res = mod_mul(res, a, n);
        a = mod_mul(a, a, n);
        b >>= 1;
    }
    return res;
}
bool miller_rabin(ll n) {
    if(n == 2 || n == 3 || n == 5 || n == 7 || n == 11)    return true;
    if(n == 1 || !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11))    return false;
    ll x, pre, u;
    int i, j, k = 0;
    u = n - 1;  
    while(!(u&1)) {    
        k++; u >>= 1;
    }
    srand((ll)time(0));
    for(i = 0; i < 20; ++i) {    
        x = rand()%(n-2) + 2;   
        if((x%n) == 0)    continue;

        x = mod_exp(x, u, n);    
        pre = x;
        for(j = 0; j < k; ++j) {
            x = mod_mul(x, x, n);
            if(x == 1 && pre != 1 && pre != n-1)    return false;   
            pre = x;
        }
        if(x != 1)    return false; 
    }
    return true;
}

int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t;
	scanf("%d",&t);
	ll n;
	while(t--) {
		scanf("%lld",&n);
		if(n%2 == 0) {
			if(n == 2) printf("1\n");
			else printf("2\n");
		}
		else {
			if(miller_rabin(n)) printf("1\n");
			else if(miller_rabin(n-2)) printf("2\n");
			else printf("3\n");
		}
	}
}

C++版本二

哥德巴赫猜想

大于二的偶数可以分解为两个素数之和；

大于七的奇数可以分解为三个素数之和；（是一定可以分解成三个素数之和，也有可能分解成两个）分解成两个必然有一个是2，其他就是至少三个。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=10000;
ll t,n,m;
int a[N];
bool prime(int x){
     for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
        return 0;
     return 1;
 
}
int main()
{
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        if(prime(n)||n==1||n==2||n==3)
             cout << 1 << endl;
        else if(n%2==0||prime(n-2))
             cout << 2 << endl;
        else
             cout << 3 << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}