Java中ArrayList.get()要求索引为int而非long的问题如何解决

问题根源 #

你混淆了集合元素泛型类型和集合索引类型的概念：

• ArrayList的<Long>泛型仅约束列表存储的元素类型为Long，和索引的类型没有任何关联
• Java中数组的长度本身就被限制为int类型，而ArrayList底层基于数组实现，因此它的get()方法入参、size()返回值天然就是int类型，最大支持的列表长度就是Integer.MAX_VALUE（约21亿），不可能支持超出int范围的索引值。

修复方案 #

1. 适配现有代码（推荐） #

你当前的循环变量使用long完全是多余的：listOfPrimes.size()返回值本身就是int，直接把循环变量改成int类型即可省去强制转换，修改后遍历逻辑如下：

// 反向遍历找最大因数
for (int i = listOfPrimes.size() - 1; i >= 0; i--) {
    if (maxNum % listOfPrimes.get(i) == 0) {
        System.out.println("Max Prime Factor is: " + listOfPrimes.get(i));
        break;
    }
}

2. 超大数据量场景 #

如果你确实需要存储超过21亿个元素，ArrayList本身已经无法满足需求，你可以自行实现支持long类型索引的集合：底层采用多段数组分片存储，避开单个数组长度不能超过int上限的限制。

额外优化建议 #

你当前的实现逻辑效率极低，完全不需要提前存储所有小于maxNum/2的质数，也根本不会遇到列表长度超出int上限的问题，优化后的最大质因数计算逻辑可以参考如下实现：

public class LargestPrimeFactor {
    public static long findLargestPrimeFactor(long num) {
        long largestPrime = 2;
        // 先把所有2的因数除干净
        while (num % 2 == 0) {
            num /= 2;
        }
        // 从3开始遍历奇数，到sqrt(num)为止
        for (long i = 3; i <= Math.sqrt(num); i += 2) {
            while (num % i == 0) {
                largestPrime = i;
                num /= i;
            }
        }
        // 如果最后剩下的num是大于2的质数
        if (num > 2) {
            largestPrime = num;
        }
        return largestPrime;
    }

    public static void main(String[] args) {
        long maxNum = 600851475143L;
        System.out.println("Max Prime Factor is: " + findLargestPrimeFactor(maxNum));
    }
}

这个实现不需要存储大量质数，时间复杂度和空间复杂度都远低于你当前的版本，完全支持处理long取值范围内的数值。

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