首先分析何时不能尽行操作:当该集合中只剩下质数时操作结束。
因此我们只需要计算分解质因数的次数就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; }