Java奇因数判断程序对输入1099511627776无终止问题求助

核心问题根源 #

你输入的1099511627776是**2的40次幂（即2^{40）**，这个数没有任何大于1的奇因数。程序进入偶数分支后，会执行从`j=3`到`j<=n/2`的循环（`n/2`等于549755813888），循环次数约为2.7×10}11次——这个量级的循环根本不可能在合理时间内跑完，所以程序看起来“无法终止”。

为什么修改最后一位就正常？ #

修改最后一位后，这个数不再是纯2的幂：

• 如果改成奇数，会直接触发n%2!=0的判断，输出YES；
• 如果改成包含奇因数的偶数，循环会很快找到第一个能整除它的奇数，执行break跳出循环，自然能正常输出结果。

程序低效点与优化方案 #

你当前的偶数分支遍历逻辑效率极低，尤其是遇到2的幂这种最坏情况时完全不可用。其实判断是否存在大于1的奇因数，只需要一个更简单高效的逻辑：把数字中所有2的因子全部移除，剩下的数如果大于1，就说明存在奇因数；如果等于1，说明是纯2的幂，没有符合要求的奇因数。

优化后的代码如下：

import java.util.Scanner;
public class Simple1{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        long n;
        for(int i=0; i<t; i++) {
            n=sc.nextLong();
            if(n<3)System.out.println("NO");
            else {
                if(n%2!=0)System.out.println("YES");
                else {
                    // 移除所有2的因子
                    long temp = n;
                    while (temp % 2 == 0) {
                        temp /= 2;
                    }
                    // 根据剩余值判断结果
                    System.out.println(temp > 1 ? "YES" : "NO");
                }
            }
        }
        sc.close();
    }
}

这个优化后的版本，哪怕处理2^100这样的超大数，也只需要几十次除法操作就能得出结果，完全不会出现卡死的情况。测试1099511627776时，会直接输出NO，瞬间完成。

内容的提问来源于stack exchange，提问作者Jahirul Sarker