2
\$\begingroup\$

I wanted a reusable class for generating a list of primes till some arbitrary (but reasonable) limit. So, I wrote a class Primes that implements the Sieve of Eratosthenes and another method that makes use of this sieve. The implementation is done on the basis of clarity and swiftly obtaining results.

I admit that using a BitSet would have improved memory usage and using the Sieve of Atkin would have given me a (slightly) better runtime, but I avoided extra trouble and went for it.

Primes.java

/**
 * This is a utility class that contains methods related to prime numbers
 * that are used in many problems in Project Euler.
 *
 * @author Subhomoy Haldar
 * @version 1.0
 */
public class Primes {

    /**
     * Returns a boolean array that is essentially a sieve. In order to check
     * if a number is prime, check if the boolean at that index is true. For
     * example,
     * <pre><code>
     *  // ...
     *  boolean[] sieve = Prime.siftTill(someLimit);
     *  int n = (yourNumber);
     *  if (sieve[n])
     *      // ... do operations with the prime number
     *  // ...
     * </code></pre>
     * <p>
     * <h2>Time complexity:</h2>
     * O(n log log n)
     * <h2>Space complexity:</h2>
     * O(n)
     *
     * @param n The number till which the sieve must be generated.
     * @return The sieve in the form of a boolean array.
     */
    public static boolean[] siftTill(int n) {
        // create an array of size (n + 1), to include the index n as well
        boolean[] sieve = new boolean[++n];
        // the outer loop will be limited to ~ sqrt(n) iterations
        int limit = (int) Math.sqrt(n);
        // initially set all to true except 0 and 1
        for (int i = 2; i < n; i++) sieve[i] = true;
        // start from 2 and remove all multiples of primes
        for (int i = 2; i < limit; i++) {
            if (sieve[i]) {
                for (int j = i * i; j < n; j += i) {
                    sieve[j] = false;
                }
            }
        }
        return sieve;
    }

    /**
     * Returns an array of primes upto the given inclusive limit.
     * <p>
     * <h2>Time complexity:</h2>
     * O(n)
     * <h2>Space complexity:</h2>
     * O(n)
     *
     * @param limit The inclusive upper limit.
     * @return An array of primes upto the given inclusive limit.
     */
    public static long[] getPrimesTill(int limit) {
        boolean[] isPrime = siftTill(limit);
        // 1st pass: count the number of primes
        int count = 0, index = 0;
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i])
                count++;
        }
        long[] primes = new long[count];
        // 2nd pass: store the primes
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i])
                primes[index++] = i;
        }
        return primes;
    }
}

I welcome comments on all aspects of the code.

\$\endgroup\$
3
\$\begingroup\$

Documentation

The class shouldn't mention who the intended client is, just what it does.

Most of your comments inside methods are noise. Document why, not what.

Error Handling

You don't handle bad inputs (e.g. negative values). It doesn't make sense for siftTill() to return an ArrayIndexOutOfBoundsException in that case. Explicitly throw a relevant exception, like IllegalArgumentException.

Naming

You use 'till' as an abbreviation for 'until'. Don't! A "till" is a real word which means something different, and it may be confusing, especially since 'until' only has one 'l'.

Best Practices

Don't reassign method parameters.

Declare variables as close as possible to their first use.

Don't use increment/decrement operations inside array references. Junior programmers will not be able to tell the order of operations.

It doesn't make sense to have a getPrimesTill() take an int as the maximum value but return a long[].

You're better off keying loops off of the array's size explicitly, rather than the variable you used to set its length. That way, if either changes your array traversal won't break.

The Primes class should be final and have a private constructor to indicate it should not be instantiated. Alternately, make an instantiable class that can be optionally be reused and runs the sieve for numbers it hasn't yet computed. That lets you keep computed information, such as the number of primes, in a member variable rather than having to walk your sieve array to find it.

Putting it all together might look something like:

import java.util.Arrays;

/**
 * This is a utility class that contains methods related to prime numbers.
 *
 * @author Subhomoy Haldar
 * @version 1.0
 */
public final class Primes {

    /**
     * Returns a boolean array that is essentially a sieve. In order to check
     * if a number is prime, check if the boolean at that index is true. For
     * example,
     *
     * <pre>
     * <code>
     *  // ...
     *  boolean[] sieve = Prime.siftTill(someLimit);
     *  int n = (yourNumber);
     *  if (sieve[n])
     *      // ... do operations with the prime number
     *  // ...
     * </code>
     * </pre>
     * <p>
     * <h2>Time complexity:</h2>
     * O(n log log n)
     * <h2>Space complexity:</h2> O(n)
     *
     * @param n The number until which the sieve must be generated.
     * @return The sieve in the form of a boolean array.
     */
    public static boolean[] siftUntil(final int n) {

        final boolean[] sieve = new boolean[n + 1];
        Arrays.fill(sieve, true);
        sieve[0] = false;
        sieve[1] = false;

        removePrimeMultiplesFrom(sieve);

        return sieve;
    }

    private static void removePrimeMultiplesFrom(final boolean[] sieve) {
        final int limit = (int) Math.sqrt(sieve.length);
        for (int i = 2; i < limit; i++) {
            if (!sieve[i]) {
                continue;
            }

            for (int j = i * i; j < sieve.length; j += i) {
                sieve[j] = false;
            }
        }
    }

    /**
     * Returns an array of primes up to the given inclusive limit.
     * <p>
     * <h2>Time complexity:</h2>
     * O(n)
     * <h2>Space complexity:</h2> O(n)
     *
     * @param limit The inclusive upper limit.
     * @return An array of primes up to the given inclusive limit.
     */
    public static int[] getPrimesUntil(final int limit) {

        final boolean[] isPrime = siftUntil(limit);

        final int[] primes = new int[countPrimes(isPrime)];
        for (int i = 2, primeIndex = 0; i <= limit; i++) {
            if (isPrime[i]) {
                primes[primeIndex] = i;
                primeIndex++;
            }
        }
        return primes;
    }

    private static int countPrimes(final boolean[] isPrime) {
        int count = 0;
        for (int i = 2; i < isPrime.length; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        return count;
    }

}
\$\endgroup\$
  • \$\begingroup\$ Nice trick using Arrays.fill(). I understand that you support separation of concerns. But isn't counting primes a bit too trivial to have its own method? \$\endgroup\$ – Hungry Blue Dev Nov 13 '15 at 17:27
  • \$\begingroup\$ @ambigram_maker I was wishy-washy on that. :-) I split it out because the OP felt strongly enough about it to add the inline comment. \$\endgroup\$ – Eric Stein Nov 13 '15 at 17:42
  • \$\begingroup\$ I vehemently commented because I feared that I wouldn't be able to read my own code a few years later. Me and my stupid paranoia. Anyway... My next GitHub commit is definitely going to incorporate a lot of major changes based on your valuable comments. ;-) \$\endgroup\$ – Hungry Blue Dev Nov 13 '15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.