Re: [Algorithm] Sum of Primes < 1000000

Patricia Shanahan schrieb:


Well, that is strange. I have been using a boolean[], and using BitSet actually
slows it down on my machine. I am using a Laptop, so CPU speed may vary. Today
it is even faster than yesterday. The output was (code see below):

Time : 42ms
Sum : 37551402022

Apart from that, from your other post I saw that you have used a different
argument to obtain the n log n upper bound.

- Your argument: There are only log n primes below n and each iteration takes
time at most n.
- My argument: Consider the iteration in which we erase prime i. We erase n/i
composite numbers. In total, we need time

   sum(i=1..n) n/i
 = n * H(n)
 = O(n * log n)

(Here, H(n) is the n-th harmonic number.) Can we combine both arguments to
obtain an upper bound below n * log n? In my sum, only log n terms are actually
necessary, as has been argued by Patricia. Unfortunately, the terms that are
actually present are the larger ones (those for small i). Still, some Googling
reveals that it is possible to get the time down to n * log log n.

Cheers,
Simon

This is my code:

public class Primes {

    private boolean[] numbers;
    private long sum = 0;

    public Primes(int size) {
    numbers = new boolean[size];
    }

    public void eraseComposite() {
    int prime = 2;
    while (prime < numbers.length) {
        sum += prime;
        // mark multiples of prime
        for (int i = 2 * prime; i < numbers.length; i += prime) {
                // (we could start with prime*prime here, but I didn't bother
                // since it would be larger than Integer.MAX_INTEGER)
        numbers[i] = true;
        }
        // move forward to next prime
        prime++;
        while (prime < numbers.length-1 && (numbers[prime])) {
        prime++;
        }
    }
    }

    public static void main(String[] argv) {
    long t = System.currentTimeMillis();
    Primes p = new Primes(1000000);
    p.eraseComposite();
    System.out.println("Time : " + (System.currentTimeMillis() - t) + "ms");
    System.out.println("Sum : " + p.sum);
    }
}