质数（质数又称素数)是指在大于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;
}