Time Limit: 1000 MS Memory Limit: 131072 KB Total Submission(s): 40 Accepted Submission(s): 2
Description
陆历川住在北望村，村头的小卖部是陆历川经常去的地方，一天陆历川来到小卖部
老板：“买啥子呦？”
陆历川：“买锤子撒。”
老板：“啥子类型的锤子呦？”
吧啦吧啦一顿说，陆历川挑好了要买的锤子，一共是4块钱，但是这个小卖部的老板总是喜欢搞一些优惠。
今天的优惠方式是，收取的金额为该金额除了其自身以外的最大因子，因为陆历川可以分多次付款，所以他可以把这次的钱分两次付款
每次付款金额是2元，这样的话他就可以利用优惠，使自己花2元就可以买到锤子了。
现在陆历川想知道，给定任意金额，他最后最少要交多少钱给老板
Input
输入金额n(2 <= n <= 1e8)
Output
题目要求
Sample Input
2 3 4
Sample Output
1 1 2
Source
Unknown
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int isprime(int num) { if(num == 3||num == 2) return true; if(num%6!=1&&num%6!=5) return false; for(int i = 5; i*i <= num; i += 6) { if(num % i == 0||num % (i+2) == 0) return false; } return true; } int main() { int n; while(scanf("%d", &n) != EOF) { if(n == 2||n == 3) printf("1\n"); else if(n%2==0) printf("2\n"); else if(isprime(n)) printf("1\n"); else { if(isprime(n-2)) printf("2\n"); else printf("3\n"); } } return 0; } 判断是否为素数方法证明： 首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等； 证明：令x≥1，将大于等于5的自然数表示如下： ······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······ 可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里有个题外话，关于孪生素数，有兴趣的道友可以再另行了解一下，由于与我们主题无关，暂且跳过。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。 根据以上规律，判断质数可以6个为单元快进