Re: NegativeArraySizeException ... IndexOutOfBoundsException ...

From:

markspace <nospam@nowhere.com>

Newsgroups:

comp.lang.java.programmer

Date:

Sat, 02 Jan 2010 12:10:24 -0800

Message-ID:

<hho97l$a60$1@news.eternal-september.org>

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() );
     }