Nancy喜欢博奕！ Johnson和Nancy得到了一个神奇的多重集合，仅包含一个正整数n，两个人轮流进行操作。 一次操作可以将集合中一个数字分解为它的任意两个非1的因数，并加入集合中，当谁无法执行此步操作时，对方获胜。 他们想知道，在Johnson和Nancy绝顶聪明的情况下，如果Nancy先手进行操作，最后的败者是谁？ 输入描述: 第一行：一个整数n。 数据满足： 1 ≤ 𝑛 ≤ 95718 1≤n≤95718。 输出描述: 共一行：一个字符串，表示最后的败者（Johnson或者Nancy）。 示例1 输入 复制 4 输出 复制 Johnson #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int cnt=0; for(int i=2;i<=sqrt(n);i++) { while(n%i==0) { cnt++; n=n/i; } } if(n!=1){ cnt++; } if(cnt%2==0){ printf("Johnson\n"); } else{ printf("Nancy\n"); } return 0; } 要用到唯一分解定理：一个合数一定可以分解为唯一的有限个素数的乘积. 外层循环主要是提供可能为分解素数的所有可能 内层判断是不是n的素数，是的话就除以i。分解出的素数就加一，再判断i是不是除后的数的因数。 除到最后要看最后一个乘积的因数是不是一是的话就说明分解就是当前的cnt不是一的话就说明最后一个数也是乘积中的素数因子cnt+1。