质数(质数又称素数)是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
1、在一个大于1的数a和它的2倍之间(即区间(a, 2a]中)必存在至少一个素数。
2、存在任意长度的素数等差数列。 [1]
3、一个偶数可以写成两个合数之和,其中每一个合数都最多只有9个质因数。(挪威数学家布朗,1920年)
4、一个偶数必定可以写成一个质数加上一个合成数,其中合数的因子个数有上界。(瑞尼,1948年)
5、一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来,有人简称这结果为 (1 + 5)(中国潘承洞,1968年)
6、一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2)
1.判断质数

int isPrime(int n){//1不是素数,所以要先判断传入的参数是否为1 if(n==1){//如果为1则返回0 return 0;}else{//sqrt()函数需要cmath头文件 for(int i=2;i<=sqrt(n);i++){if(n%i==0){return 0;}}//没有在2~m-1之间找到n的商,证明此数是素数,返回1 return 1;}}

2.求最大质因子

int GetMax(int a)//求数字a的最大质因子
{if(a==1)return 1;else{for(int i=2; i*i<=a; i++){if(a%i==0){return GetMax(a/i)>GetMax(i)?GetMax(a/i):GetMax(i);}}return a;}
}

3.判断数字n是不是质数×质数的形式

bool check(int n)//判断数字n是不是质数×质数的形式
{int i;for(i=2; i<=sqrt(n); i++)if(n%i==0)if(factor[i]&&factor[n/i])return true;return false;
}

4.素数打表

/*bool is_prime[100010];
bool factor[100010];
int p,book[100010];*/全局
void prime(int n)//从1-n的素数表
{int i,j;memset(factor,true,sizeof(factor));factor[0]=factor[1]=false;for(i=2; i<=n; i++){if(factor[i])book[p++]=i;for(j=0; j<p&&book[j]*i<=n; j++){factor[book[j]*i]=false;if(i%book[j]==0)break;}}
}

5.质数的son
题目大意:a和b两个人玩游戏,a给了我们钱(大雾)所以我们要让a赢。给一个数字,两个人轮流取这个数的真因数(不能包含1和这个数本身),谁不能取了谁就赢。(a先取)

样例解释:3这个数字没有真因数,所以a没法取,a直接获胜,输出0。4这个数字的真因数只有2,所以a取2,然后轮到b取,2这个数字没有真因数,所以b没法取了,b获胜输出-1。8这个数字,a先取4,然后b取2,然后a没法取了,a获胜。(如果a获胜的开局有多个就输出数字最大的那一个),666这个数字,a先取111,然后b只能取3或者37,这两个数字都没有真因数,所以a获胜。

解题思路:其实归根到底就是看到最后的那个数字是不是质数,如果谁先取到质数谁就输了,因为下一个人一定没办法再取了,所以我们尽量要让b取到质数(谁让我们收a的黑钱了呢)。

首先我们假设b最后取的质数是k,那么这个k应该是所给数字n的最大质因子,为什么呢?
1.我们要让b取质数,2.我们要让a开局取得数字尽量大,这样一来如果b取得的是最大质因子,那么就可以保证上面两种情况.
我们再看666那个例子,到最后b只能从111中取真因数,而111这个数字的真因数只有37和3,所以b只能取质数。同理我们可以让a选的那个数字是两个质数相乘的形式,这样一来b只能从两个质数里面选,不管他选什么,他都是输定了,而37刚好是666的最大质因数,没错!这就是关键,a所选的那个数字=一个质数×所给数字n的最大质因数。那么这”一个质数“怎么求呢,题目说了要让a取的数字尽量大,所以我们也要让这”一个质数“尽量大,同时我们需要满足n%(一个质数*n的最大质因数)=0,也就是说你a取得数字得是n的真因数。另外如果数字n一开始就是质数的话直接输出0(a必赢),如果数字n是质数×质数的形式的话直接输出-1(a必输,因为我们就是用这种方法对付b的)。

#include <bits/stdc++.h>using namespace std;
bool is_prime[100010];
bool factor[100010];
int p,book[100010];
void prime(int n)//从1-n的素数表
{int i,j;memset(factor,true,sizeof(factor));factor[0]=factor[1]=false;for(i=2; i<=n; i++){if(factor[i])book[p++]=i;for(j=0; j<p&&book[j]*i<=n; j++){factor[book[j]*i]=false;if(i%book[j]==0)break;}}
}int GetMax(int a)//求数字a的最大质因子
{if(a==1)return 1;else{for(int i=2; i*i<=a; i++){if(a%i==0){return GetMax(a/i)>GetMax(i)?GetMax(a/i):GetMax(i);}}return a;}
}bool check(int n)//判断数字n是不是质数×质数的形式
{int i;for(i=2; i<=sqrt(n); i++)if(n%i==0)if(factor[i]&&factor[n/i])return true;return false;
}int main()
{int t,n,i;scanf("%d",&t);prime(100010);//处理素数表while(t--){scanf("%d",&n);if(GetMax(n)==n)//如果一个数字的最大素数因子是他本身,那么他就是个素数printf("0\n");else if(check(n))printf("-1\n");else{for(i=n/GetMax(n); i>=2; i--)//倒着找,从大到小找,找到满足条件的直接breakif(factor[i]&&n%(i*GetMax(n))==0){printf("%d\n",i*GetMax(n));break;}}}return 0;
}