Java质数倍数生成程序整数溢出与数组越界问题排查求助

我来帮你拆解一下这个问题的核心原因，以及对应的修复方案：

1. 看似「i跳变」的真相：中间循环未触发打印 #

你看到i从11直接跳到997438，并不是i真的跳变了——而是当i超过11之后，i*2153的结果已经大于25000（比如i=12时，2153*12=25836>25000），所以if(i*k <=n)的条件不成立，System.out.println没有执行。直到i增大到某个值，i*k发生整数溢出变成负数，这时候负数肯定小于25000，条件重新成立，才会再次打印输出，看起来像是i突然跳了一大步。

2. 整数溢出与数组越界的根本原因 #

整数溢出 #

Java的int是32位有符号整数，最大值为2147483647。当k=2153，i=997438时，2153*997438的计算结果超过了这个最大值，触发溢出，结果变成负数（补码规则下的循环溢出）。这时候i*k <=25000会被判定为true，导致你尝试访问array[负数索引]，直接抛出ArrayIndexOutOfBoundsException。

循环终止条件错误 #

内层循环用i < 1000000作为终止条件完全不合理——这会让i一直递增到接近100万，完全没必要，而且必然会触发溢出。正确的终止条件应该是确保i*k不超过n，同时还要避免溢出风险。

数组长度不足 #

你初始化的boolean[] array = new boolean[25000];的索引范围是0~24999，但当n=25000时，i*k可能等于25000（比如k=2，i=12500），这时候访问array[25000]也会触发越界异常。

修正后的代码 #

质数判断函数（逻辑没问题，保持不变） #

protected boolean isPrime(int number) {
    if (number == 2 || number == 3) return true;
    // check if n is a multiple of 2
    if (number % 2 == 0) return false;
    // if not, then just check the odds
    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) return false;
    }
    return true;
}

修正后的倍数生成代码 #

int n = 25000;
// 数组长度设为n+1，确保能容纳索引0~n
boolean[] array = new boolean[n + 1]; 

for (int k = 2; k <= n; k++) {
    if (isPrime(k)) {
        // 用i <= n/k作为终止条件，避免溢出，同时精准控制i的范围
        for (int i = 1; i <= n / k; i++) { 
            int multiple = i * k;
            System.out.println("k: " + k + " i: " + i + " k*i: " + multiple);
            array[multiple] ^= true;
        }
    }
}

关键修复点说明 #

• 把数组长度改为n+1，确保所有i*k <=n的倍数都有对应的合法数组索引。
• 内层循环终止条件改为i <= n/k：这样既保证了i*k <=n，又避免了直接计算i*k导致的溢出问题（因为n/k是整数除法，结果不会超过n，远小于int的最大值）。
• 把i的起始值从0改为1：因为i=0时i*k=0，通常我们不需要处理0这个倍数（除非你的业务需求特殊），而且能减少一次无意义的计算。

这样修改后，程序就不会再出现溢出和越界问题，也不会有看似「i跳变」的奇怪输出了。

内容的提问来源于stack exchange，提问作者J Doe