Windowed Sieve of Eratosthenes in Java

Question

I wanted to try and use the Sieve of Eratosthenes to find all prime numbers between some arbitrary bounds 1 <= m <= n. The simple implementation of the sieve does not consider the lower bound at all, it always starts from 1 (or actually from 2). So for a big enough n, simply creating an array would be impossible.

The algorithm first finds all prime numbers from 1 to sqrt(n), then uses those numbers to find all primes in the given range.

I'd like to know if:

I'm using more memory than necessary
I'm unnecessarily repeating some operations
I can improve the style of this code

Note: I am not validating user input for simplicity sake.

import java.util.*;

public class PrimeLister {

    private static ArrayList<Integer> segmentSieve(int upperBound) {
        boolean[] primes = new boolean[upperBound + 1];
        Arrays.fill(primes, true);
        ArrayList<Integer> numbers = new ArrayList<>();

        for (int i = 2; i <= upperBound; i++) {
            if (!primes[i])
                continue;
            for (int j = i * i; j <= upperBound; j += i) {
                primes[j] = false;
            }

            if (primes[i])
                numbers.add(i);
        }

        return numbers;
    }

    private static int findOffset(int start, int prime) {
        for (int i = 0; i < prime; i++)
            if (start++ % prime == 0)
                return i;
        return -1;
    }

    public static void listPrimes(int lowerBound, int upperBound) {
        ArrayList<Integer> segmentPrimes = segmentSieve((int) Math.floor(Math.sqrt(upperBound)));
        int[] offsets = new int[segmentPrimes.size()];
        boolean[] primes = new boolean[1 + upperBound - lowerBound];
        Arrays.fill(primes, true);

        for (int i = 0; i < offsets.length; i++) {
            int tmp = segmentPrimes.get(i);
            offsets[i] = findOffset(lowerBound, tmp);

            for (int j = offsets[i]; j < primes.length; j += tmp) {
                if (!primes[j] || (j + lowerBound) == tmp)
                    continue;
                primes[j] = false;
            }
        }

        for (int i = 0; i < primes.length; i++) {
            if (primes[i] && (i + lowerBound) != 1)
                System.out.println(i + lowerBound);
        }

        System.out.println();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int lowerBound = in.nextInt();
        int upperBound = in.nextInt();
        listPrimes(lowerBound, upperBound);
        in.close();
    }
}

DarthGizka · Accepted Answer · 2015-12-04 11:44:22Z

What makes your code difficult to read is nonsense (in the sense of 'carries no meaning') like int tmp, or stuff like the condition (j + lowerBound) == tmp. The superfluous parentheses are just noise but j + lowerBound does not make sense at all, as it corresponds to offsetting the current index j into the window by the window's lower bound. lowerBound + j would make sense, as it corresponds to the actual number represented by the jth slot of the window. The fact that operator + is commutative is beside the point; it's humans who must understand your code. And your code is so difficult to understand that you don't even understand it fully yourself! Trying to express code with the greatest possible clarity can be a great aid in understanding the problem under consideration; on the other hand, churning out code when the problem has not been understood achieves the opposite effect.

The problem under consideration has no need of arrays containing offsets into the window. The algorithm just needs one offset during each iteration of the outer loop, just once. The computation of the offset would have warranted some 'hands-free' thinking time before the actual coding.

The first location that needs to be worked on by the inner 'cross off the composites' loop is p * p, where p is the current prime; let's call this start. This value needs to be reduced to an offset within the window being worked on, which is trivial (start - lower_bound) if start >= lower_bound. If start < lower_bound then it's time to unsheath the modulo operator.

// (p is the current prime)

int stride = p << (p & 1);
int start = p * p;
int offset;

if (start >= lower_bound)
{
   offset = start - lower_bound;
}
else
{
   int before_the_segment = (lower_bound - start) % stride;

   offset = before_the_segment == 0 ? 0 : stride - before_the_segment;
}

// ...

An alternative expression for the tricky case would be

offset = (stride - (lower_bound - start) % stride) % stride

but it leaves no clue for the reader as to what's intended... This can be simplified further to drop one module operator, by careful consideration of the magnitudes involved. But it is easy to shoot oneself in the foot. If there's no pressing need for shaving cycles then it's better to leave the simpler - if more verbose - code in place.

The original code uses the prime p itself as stride, which has the effect that all even composites get crossed off multiple times (first during the run with p = 2, and then again during all even steps during the runs with other primes). This means that the code does almost double the amount of work that's necessary.

A simple fix is to use p + p as stride when p <> 2. In effect this amounts to using a two-spoke wheel and ignoring the even spoke entirely except for its one lone prime occupant (the number 2). Another solution - which halves memory consumption - would be to represent only the even numbers in the sieve array and to pull the only even prime out of thin air when needed. Higher-order wheels would further reduce memory consumption and the amount of work done, but they would complicate the code considerably. By contrast, the two-spoke wheel gives a lot of bang while adding only one minuscule complication to the code.

Stack Exchange Network

Windowed Sieve of Eratosthenes in Java

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Windowed Sieve of Eratosthenes in Java

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions