Re: Sum of Primes < 1000000

From:

"Daniel Pitts" <googlegroupie@coloraura.com>

Newsgroups:

comp.lang.java.programmer

Date:

5 Jan 2007 13:18:02 -0800

Message-ID:

<1168031882.231562.224100@s80g2000cwa.googlegroups.com>

Patricia Shanahan wrote:

Simon wrote:

Luc The Perverse schrieb:

I was messing around on a site where you answer questions for points. (No
prizes or anything)

Anyway, they say our programs *should* execute in less than 1 minute if well
formed.

Mine didn't - it was less than 10 minutes though and I got the right answer.

I was supposed to sum all primes less than 1 million.

Is there an algorithm out there, which I will be able to understand, which
works significantly faster than this one?

You may want to have a look at the Sieve of Eratosthenes (and its successors)
(see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). It finds all primes up
to n in time n log n. On my computer my implementation takes 150 milliseconds
for n=1000000.

As a matter of curiosity, did you use a boolean[] or BitSet?

I started with a boolean[], and mine was slower than yours, about 200
milliseconds. It dropped to under 100 milliseconds when I switched to
BitSet. I believe the improvement is due to more efficient caching.

Patricia

I personally got 66ms from:

public class SumPrimes {
    public static void main(String...args) {
        final int bounds = Integer.parseInt(args[0]) + 1;
        final java.util.BitSet composits = new
java.util.BitSet(bounds);
        long sum = 1;
        for (int prime = 2; prime < bounds; prime =
composits.nextClearBit(prime +1)) {
            sum += prime;
            for (int composit = prime + prime; composit < bounds;
composit += prime) {
                composits.set(composit);
            }
        }
        System.out.println(sum);
    }
}