首先分析何时不能尽行操作:当该集合中只剩下质数时操作结束。
因此我们只需要计算分解质因数的次数就OK了。本体比较菜,所以搞了一个欧拉筛来计算质数,显然有点大材小用。

#include <bits/stdc++.h>

using namespace std;
const int N = 3e7+5;
int p[N], cnt;
bool vis[N];/// 1 表示合数 0 表示素数
void Euler(int n)
{
   cnt = 0;
   for(int i = 2; i <= n; ++i)
   {
       if(!vis[i])
            p[++cnt] = i;
       for(int j = 1; j <= cnt && p[j] * i <= n; ++j)
       {
            vis[ p[j] * i ] = 1;
            if(i % p[j] == 0)/// 确保每个合数只被它的最小质因子筛掉
               break;
       }
   }
}
int main()
{

    int n;
    scanf("%d",&n);
    Euler(n);
    int sum = 1;
    while(vis[n])
    {
        for(int i = 2;i <= n / 2;++i)
        {
            if(!vis[i]&&n % i == 0)
            {
                sum++;
                n /= i;
                break;
            }
        }
    }
    //printf("%d\n",sum);
    if(sum % 2 == 0) printf("Johnson\n");
    else printf("Nancy\n");
    return 0;
}