题目描述
Nancy喜欢博弈！
Johnson和Nancy得到了一个神奇的多重集合，仅包含一个正整数n，两个人轮流进行操作。
一次操作可以将集合中一个数字分解为它的任意两个非1的因数，并加入集合中。
他们想知道，在Johnson和Nancy绝顶聪明的情况下，如果Nancy先手进行操作，最后谁没有办法继续操作了呢？
输入描述:
第一行：一个整数n。
数据满足：1<=n<=95718
输出描述:
共一行：一个字符串，表示最后谁（Johnson或者Nancy）无法进行操作。
思路：
这道题考察算数基本定理，算数基本定理的概念如下：

算数基本定理：
任何一个大于1的自然数 N ，如果 N不为质数，都可以 唯一分解成有限个质数；
这个定理的证明比较繁琐，而且对于我们做题没什么实际的研讨价值，有兴趣的同学可以在百度百科自行了解一下。
这个定理为我们提供了一些非常有用的性质。

首先，都可以 说明每个数字都是由若干个素数组成的。其次， 唯一 说明只要有一个Pi或者ai不同，那么一定对应了两个不同的 N。
所以，对这个数N分解质因数就可以了。
代码如下： 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[100000], cnt[100000];
int main()
{
	int ans = 0, res = 1;
	memset(pri, 1, sizeof(pri));
	for (int i = 2;i <= 95720;i++)
		if (pri[i])
			for (int j = i + i;j <= 95729;j+=i)
				pri[j] = 0;
	for (int i = 2;i <= 95720;i++)
		if (pri[i])
			cnt[res++] = i;
	/*for (int i = 1;i < 100;i++)
		cout << cnt[i] << " ";*/
	int n;
	cin >> n;
	if (pri[n])
	{
		cout << "Nancy" << endl;
		return 0;
	}
	int i = 1;
	while (n > 3 && i < res)
	{
		if (n % cnt[i] == 0)
		{
			ans++;
			n /= cnt[i];
            if(pri[n])
                break;
		}
		else
		{
			i++;
		}
	}
	if (ans % 2 == 1)
		cout << "Johnson" << endl;
	else
		cout << "Nancy" << endl;
	return 0;
}
求牛币，qwq。