java - 提高java中Eratosthenes代码筛的效率

Question

我已经为 Sieve of Eratosthenes 编写了代码在 Java 中，但我面临一些时间和空间效率问题。这是代码:

import java.util.*;

class EratosthenesSeive
{

    public static void main(String args[])
    {

        ArrayList<Long> myPrimeList = new ArrayList<Long>();
        ArrayList<Long> myTempPrimeList = new ArrayList<Long>();
        ArrayList<Boolean> isPrimeNumber = new ArrayList<Boolean>();
        int index = 0;

        long ul = 1500l;
        long ll = 2;

        do
        {
            myTempPrimeList.add(ll);
            isPrimeNumber.add(true);
            ll++;
        }while( ll != (ul+1));

        for(long i : myTempPrimeList)
        {
            if(isPrimeNumber.get(index))
            {
                myPrimeList.add(i);
                for(long j = i ; j*i <= ul; j++)
                {
                    isPrimeNumber.set(myTempPrimeList.indexOf(j*i),false);
                }
            }
            index++;
        }

        System.out.println(myPrimeList);
    }
}

对于高达 10^3 的输入，它似乎工作正常，在 10^4 时它只是挂起，在 10^5 及以上我得到 OutOfMemoryError .代码似乎工作正常，但我想把它固定一点。有什么建议吗？

Answer 1

您在该代码中装箱/拆箱 ton。您可能想尝试更换 ArrayList<> s 为原始类型的直数组。