判断质数的算法
P1125 [NOIP2008 提高组] 笨小猴
题目描述
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
输入格式
一个单词，其中只可能出现小写字母，并且长度小于100100。
输出格式
共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出00。
输入输出样例
| 输入 | error |
|---|---|
| 输出 | Lucky Word 2 |
| 输入 | olympic |
|---|---|
| 输出 | No Answer 0 |
说明/提示
【输入输出样例1解释】
单词error中出现最多的字母rr出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。
【输入输出样例2解释】
单词olympic中出现最多的字母i出现了1次，出现次数最少的字母出现了1次，1?1=0，00不是质数。
（本处原题面错误已经修正）
noip2008提高第一题
解题思路
开辟一个含有26个元素的int型数组存放单词中各字母的数目，统计出数组最大值maxn和最小值minn，做差得maxn-minn，判断其是否为质数。
判断质数的算法：
首先看一个关于质数分布的规律：大于等于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的相邻两侧。
另外，我们知道，一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可，因为若sqrt(n)左侧找不到约数，那么右侧也一定找不到约数。
我的代码如下：
#include
using namespace std;
int a[26];
//判断质数
bool zhi(int n)
{
if(n<5)
{
if(n==2||n==3)return 1;
else return 0;
}
if(n%6!=5&&n%6!=1)
return 0;
for(int i=5;i<=sqrt(n);i+=6)
{
if(n%i==0||n%(i+2)==0)
return 0;
}
return 1;
}
int main()
{
int maxn=0,minn=100;string w;
cin>>w;
for(int i=0;w[i]!='\0';i++)
{
int t=w[i]-'a';
a[t]++;
}
for(int i=0;i<26;i++)
{
if(a[i]>maxn)maxn=a[i];
if(a[i] 有了这一题的基础，下面的问题也迎刃而解。
1+1数学问题（from CPPU OJ）
题目描述
德国数学家哥德巴赫于1742年6月7日在给大数学家欧拉的信中提出，是不是所有的大于2的偶数，都可以表示为两个素数的和？同年6月30日，欧拉在回信中认为这个猜想可能是真的，但他无法证明。正因为如此,这个命题,称之为哥德巴赫猜想。现在，哥德巴赫猜想的一般提法是：每个大于等于6的偶数，都可表示为两个奇素数之和；每个大于等于9的奇数，都可表示为三个奇素数之和。其实，后一个命题就是前一个命题的推论。哥德巴赫猜想貌似简单，要证明它却着实不易，成为数学中一个著名的难题。18、19世纪，所有的数论专家对这个猜想的证明都没有作出实质性的推进，直到20世纪才有所突破。直接证明哥德巴赫猜想不行，人们采取了迂回战术，就是先考虑把偶数表为两数之和，而每一个数又是若干素数之积。如果把命题"每一个大偶数可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"，那么哥氏猜想就是要证明"1+1"成立。从20世纪20年代起，外国和中国的一些数学家先后证明了"9+9""2+3""1+5""1+4"等命题。1966年，我国年轻的数学家陈景润，在经过多年潜心研究之后，成功地证明了"1+2"，也就是"任何一个大偶数都可以表示成一个素数与另一个素因子不超过2个的数之和"。这是迄今为止，这一研究领域最佳的成果，距摘取这颗"数学王冠上的明珠"仅一步之遥，在世界数学界引起了轰动。"1+2"也被誉为陈氏定理。
本题让你试试把大于等于6的偶数，分解为两个奇素数之和。
输入一个大于等于6的偶数x，输出分解后的两个奇素数，小数在前，大数在后，中间空格空开。对于有些偶数，结果可能不止一个，要求输出小数最小的结果。如果无解，则输出“No”，同时你就可以获得100万美元的奖金与个人一等功一次。
解题思路
问题比较简单，并不需要了解上面的背景；同时该猜想并不会被一个程序所推翻，也不需要考虑无解的情形（100万美金和一等功应该是搞笑的。。）
故以上题干显然只有两句话有用，也就是“把大于等于6的偶数，分解为两个奇素数之和”这句话以及对输出结果的要求。
又我们根据上题了解了判断质数的好方法，故直接把整个函数复制到这题即可。
本题代码如下：
//分解大偶数
#include
using namespace std;
//判断质数
bool zhi(int n)
{
if(n<5)
{
if(n==2||n==3)return 1;
else return 0;
}
if(n%6!=5&&n%6!=1)
return 0;
for(int i=5;i<=sqrt(n);i+=6)
{
if(n%i==0||n%(i+2)==0)
return 0;
}
return 1;
}
int main()
{
int N;
cin>>N;
for(int i=3;i<=N-3;i++)
{
if(zhi(i)==1&&zhi(N-i)==1)
{
cout<