1240.北望村小卖部

Time Limit: 1000 MS    Memory Limit: 131072 KB
Total Submission(s): 62    Accepted Submission(s): 7

Description

 陆历川住在北望村，村头的小卖部是陆历川经常去的地方，一天陆历川来到小卖部
 老板：“买啥子呦？”
 陆历川：“买锤子撒。”
 老板：“啥子类型的锤子呦？”
 吧啦吧啦一顿说，陆历川挑好了要买的锤子，一共是4块钱，但是这个小卖部的老板总是喜欢搞一些优惠。
 今天的优惠方式是，收取的金额为该金额除了其自身以外的最大因子，因为陆历川可以分多次付款，所以他可以把这次的钱分两次付款
 每次付款金额是2元，这样的话他就可以利用优惠，使自己花2元就可以买到锤子了。
 现在陆历川想知道，给定任意金额，他最后最少要交多少钱给老板

Input

输入金额n(2 <= n <= 1e8)

Output

题目要求 
2
3
4

Sample Output

1
1
2

Source

Unknown

                你可知哥德巴赫猜想~~任意一个偶数可拆分成两个质数~~所以当所需的钱n，n%2==0,分别分成两个质数交就好~这样就是2块~当n%2==1时候，如果n能拆封成、2和一个质数~那么就是交2块，~~~不然就只能拆成一个质数（3）和一个偶数，而哪个偶数又能拆成2个质数，这样就是3块~~别忘了2和3的特殊判断；

               而在这个题中对于怎样快速判断一个数是否是质数~~一种是用mr函数直接判断~~另一种的话可以看这篇博客：https://blog.csdn.net/huang_miao_xin/article/details/51331710的第三个方法~~。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long int 
ll gcd(ll x, ll y)
{
	if (!y)
	{
		//	cout << "Asd" << endl;
		return x;
	}
	return (y, x%y);
}
ll pow(ll a, ll x, ll mod)//要用到快速幂
{
	ll ans = 1;
	while (x)
	{
		if (x & 1)
		{
			(ans *= a) %= mod;
		}
		(a *= a) %= mod;
		x = x / 2;
	}
	return ans;
}
bool mr(ll x)
{
	if (x == 2)
	{
		return true;
	}
	if (x == 1)
	{
		return 0;
	}
	for (ll s = 1; s <= 10; s++)//40次判断就行了
	{
		//	cout << s << endl;
		ll now = rand() % (x - 2) + 2;
		if (pow(now, x - 1, x) != 1)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	ll x;
	while (~scanf("%lld", &x))
	{
		if (x == 2)
		{
			cout << "1" << endl;
			continue;
		}
		if (x % 2 == 0)
		{
			cout << "2" << endl;
		}
		else
		{
			if (mr(x))
			{
				cout << "1" << endl;
			}
			else
			{
				if (mr(x - 2))
				{
					cout << "2" << endl;
				}
				else
				{
					cout << "3" << endl;
				}
			}
		}
	}
	return 0;
}