Java程序优化：高效判断数字是否存在大于1的奇数因子-java教程-PHP中文网

Java程序优化：高效判断数字是否存在大于1的奇数因子

心靈之曲

发布： 2025-10-28 11:39:01

原创

831人浏览过

Java程序优化：高效判断数字是否存在大于1的奇数因子

本文探讨了在java中判断一个长整型数字是否存在大于1的奇数因子的优化方法。针对原始代码在处理大型2的幂次时出现的性能瓶颈，文章提出了两种更高效的解决方案：一是通过反复除以2直到获得一个奇数，二是利用位运算 `n & (n-1)` 快速判断一个数是否为2的幂次。这些优化策略能显著提升程序在大数场景下的执行效率。

原始方法及其性能瓶颈分析

在判断一个数字 n 是否存在大于1的奇数因子时，一个直观的思路是遍历从3开始的所有奇数，直到 n/2，检查它们是否能整除 n。以下是这种思路的Java实现示例：

import java.util.Scanner;

public class Simple1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 测试用例数量
        for (int i = 0; i < t; i++) {
            long n = sc.nextLong(); // 输入数字
            if (n < 3) { // 1和2没有大于1的奇数因子
                System.out.println("NO");
            } else {
                if (n % 2 != 0) { // 奇数本身就是大于1的奇数因子
                    System.out.println("YES");
                } else {
                    int ans = 0; // 标记是否找到奇数因子
                    // 遍历从3开始的奇数，直到 n/2
                    for (long j = 3; j <= n / 2; j += 2) {
                        if (n % j == 0) {
                            ans = 1;
                            break; // 找到即退出
                        }
                    }
                    if (ans == 1) {
                        System.out.println("YES");
                    } else {
                        System.out.println("NO");
                    }
                }
            }
        }
        sc.close();
    }
}

登录后复制

这段代码对于大多数输入都能正常工作，但在处理特定输入，例如 n = 1099511627776 时，程序会长时间无响应，表现为“不终止”或“无输出”。这个数字实际上是 $2^{40}$。

问题的根源在于，当 n 是一个纯粹的2的幂次（例如 $2^{40}$、$2^{41}$ 等）时，它不包含任何大于1的奇数因子。在这种情况下，上述代码中的 for 循环 for(long j=3; j<=n/2; j+=2) 将会从3一直迭代到 n/2。对于 $n = 2^{40}$，n/2 等于 $2^{39}$。这意味着循环将执行大约 $2^{39} / 2 = 2^{38}$ 次迭代。这是一个极其庞大的数字（约 $2.7 \times 10^{11}$），导致程序执行时间过长，从而出现假性“不终止”的现象。这种效率问题对于任何大的2的幂次都会发生，例如 $2^{39}$ 或 $2^{41}$。

优化方案一：连续除以2

一个更高效的方法是利用数字的性质：如果一个偶数 n 存在大于1的奇数因子，那么这个因子也必然是 n 连续除以2直到变成一个奇数后的结果的因子。换句话说，我们可以不断地将 n 除以2，直到 n 变为一个奇数。如果最终得到的奇数大于1，则原数存在大于1的奇数因子；如果最终变为1，则原数是2的幂次，不存在大于1的奇数因子。

立即学习“Java免费学习笔记（深入）”；

import java.util.Scanner;

public class Simple2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            long n = sc.nextLong();

            // 循环将 n 除以 2，直到 n 变为奇数或 n <= 1
            while (n > 1 && n % 2 == 0) {
                n /= 2;
            }

            // 如果最终的 n 大于 1，说明它是一个奇数且大于1，即找到了奇数因子
            if (n > 1) {
                System.out.println("YES");
            } else { // 否则 n 变为 1，表示原数是2的幂次（或1本身）
                System.out.println("NO");
            }
        }
        sc.close();
    }
}

登录后复制

这个方法对于 $n = 2^{40}$ 只需要执行40次除法操作，相较于原始方法的 ^{38}$ 次迭代，效率提升了数万亿倍，极大地解决了性能问题。

怪兽AI数字人

数字人短视频创作，数字人直播，实时驱动数字人

查看详情

优化方案二：位运算快速判断2的幂次

判断一个数是否为2的幂次有一个非常巧妙且高效的位运算技巧。一个正整数 n 是2的幂次当且仅当 n > 0 且 (n & (n - 1)) 的结果为0。其原理是：

如果 n 是2的幂次，例如 $2^k$，那么它的二进制表示中只有最高位是1，其余位都是0（例如 $8 = 1000_2$，$16 = 10000_2$）。
n - 1 的二进制表示中，最高位变为0，其后的所有位都变为1（例如 $8 - 1 = 7 = 0111_2$，$16 - 1 = 15 = 01111_2$）。
因此，n & (n - 1) 的结果必然是0。

如果 n 不是2的幂次（且 n > 1），那么它必然包含一个大于1的奇数因子。因此，我们可以利用这个位运算来快速判断：

import java.util.Scanner;

public class Simple3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            long n = sc.nextLong();

            if (n <= 1) { // 1没有大于1的奇数因子
                System.out.println("NO");
            } else {
                // 如果 n & (n - 1) != 0，说明 n 不是2的幂次，因此它必然有大于1的奇数因子
                if ((n & (n - 1)) != 0) {
                    System.out.println("YES"); // 不是2的幂次，有奇数因子
                } else {
                    System.out.println("NO"); // 是2的幂次，没有大于1的奇数因子
                }
            }
        }
        sc.close();
    }
}

登录后复制

这个方法是最高效的，因为它仅涉及一次位运算，其时间复杂度为 $O(1)$，与输入数字的大小无关。对于任何正整数 n，它都能瞬间给出结果。