我在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。 代码似乎工作得很好,但我想更快地运行它。 有什么建议吗?