Re: NegativeArraySizeException ... IndexOutOfBoundsException ...
Arne Vajh?j wrote:
On 01-01-2010 23:58, markspace wrote:
Arne Vajh?j wrote:
Map<BigInteger,something> ....
You don't think that uses an array as backing storage?
Well, I'm assuming he's not storing every single integer, just some of
them. Maybe only primes, since non-primes could be determined by being
absent from the list.
Usually sieve means all, but maybe you are right.
I don't think so, this time. I built a small test program and the
performance was horrible. I do wonder if it was technically a sieve at all.
For posterity, here's a lousy way to sieve primes.
public static void sieve1()
{
BigInteger num = BigInteger.ZERO;
final BigInteger LIMIT = BigInteger.ONE.shiftLeft( 16 );
List<BigInteger> primes = new LinkedList<BigInteger>();
int loopCount = 0;
long startTime = System.nanoTime();
mainloop:
while( num.compareTo( LIMIT ) < 0 )
{
if( ++loopCount % 1000 == 0 )
{
System.out.println( primes.size() + " primes @ " +
((System.
nanoTime() - startTime) / 1000000) / 1000.0f +
"s" );
}
num = num.nextProbablePrime();
for( BigInteger prime : primes )
{
if( num.remainder( prime ).equals( BigInteger.ZERO ) )
{
continue mainloop;
}
}
primes.add( num );
}
System.out.println( primes.size() );
}