在java中使用long as ArrayList索引

Question

我正在编写这个java程序,使用Sieve of Eratosthenes找到所有素数达到num,但是当我尝试编译时,它说我不能使用long var作为数组索引,并且它期望一个int var in它的位置.但我会使用大数字,所以我不能使用int.我能做什么？

import java.util.*;
import java.lang.*;

public class t3{
    public static void main(String[] args){
        long num = 100;

        //declaring list and filling it with numbers
        ArrayList<Long> numlist = new ArrayList<Long>();
        for(long x=2 ; x<num ; x++){
            numlist.add(new Long(x));
        }

        //sieve or eratosthenes
        for(long x=0 ; x<Math.sqrt(num) ; x++){
            for(long y=x+1 ; y<numlist.size() ; y++){
                if(numlist[y]%numlist[x] == 0){
                    numlist.remove(y);
                }
            }
        }

        //print list
        for(Object item : numlist){
            System.out.println((Long)item);
        }
    }
}

Answer 1

我不确定为什么你的代码会编译开始.

你不应该在数组列表中使用[]来访问成员.arraylist只是一个内部存储在数组中的列表.您必须使用list get操作(仍然是O(1)).写入numlist [index]意味着你在numlist中有一个对象数组.你不能像在C++中那样覆盖[]操作.

另外,Java中的int是32位.有一个长度大于2 ^ 32的数组(所以你需要长索引)是不太可能的,我甚至不确定规范允许它.

Answer 2

通过32位signed int索引实现long [],你可以处理16GB的RAM.

如果你真的很认真地使用筛子来获得大质量数,那么你现在就不会想到几件事:

• 盒装长片的ArrayList
• 使用[]像Uri提到
• 没有系统地分页到磁盘

Answer 3

在Java规范限制阵列至多Integer.MAX_VALUE的元素.虽然a List可能包含更多元素(对于Collections 通常也是如此),但您只能使用索引添加/获取/删除/设置它们int.

假设你有很多元素的内存(我认为这不太可能),你可以编写自己的数据结构,包括"连接"数组.的get()和set()方法将采取long索引,并计算出相应的阵列和int该阵列内的索引.

此外,我建议使用布尔值来表示每个数字的状态,而不是显式地存储/删除每个数字.这样会更好,因为(1)布线占用的空间小于长,而(2 ArrayList)在元件移除期间移动元件(如所做的那样)可能很昂贵.