11
\$\begingroup\$

Task: Print sum of first 1000 primes.

public class PrimeSummation {
    public static void main(String[] args) {
        System.out.println(sumFirstPrimes(1000));
    }
    // Calculates the total of the first n primes
    public static int sumFirstPrimes(int n) {
        /* Since 2 is the only even prime it is pre-included; 
        affords convenience of skipping other evens.
        3 is as well to skip an otherwise necessary check in isPrime() */
        int result = 5, count = 2;

        for (int i = 5; count < n; i += 2) {
            if (isPrime(i)) { result += i; count++; }
        }
        return result;
    }
    /* Determines if a number is prime, commented out irrelevant checks
    remove comments for general use */
    private static boolean isPrime(int num) {
        // if (num <= 3) { return num > 1; }
        if (/*(num & 1) == 0 || */ num % 3 == 0) { return false; }

        int limit = (int)Math.sqrt(num);

        for (int i = 5; i <= limit; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) { return false; }
        }
        return true;
    }
}

I'm trying to adjust my programming style to a "people first" paradigm. While any and all feedback is welcome, that is the focus.

  1. Is there any ambiguity? Are the variable and method names adequate? I thought I could be more specific but the names would get significantly longer, is there some standard regarding the length of names?
  2. Are the comments sufficient? I structure a general purpose method, but comment out otherwise redundant checks; rendering its use distinct to the task. Given specificity it was also made private. Is this good practice?
  3. On the execution itself, is it satisfactory or are there some pitfalls I don't account for/optimizations I could make?
\$\endgroup\$
11
\$\begingroup\$

I understand your conundrum. You've set a trap: isPrime() is a bastardized implementation that produces incorrect results for 2 and 3, so you have to be careful to never call isPrime(2) or isPrime(3). If you were to add checks to handle those special cases, you would defeat your performance optimization.

Personally, I don't think that the optimization, which saves a few microseconds of execution time, is worth it. You and I have each wasted many minutes agonizing over this issue already.

If you are still committed to using that optimization, I suggest renaming the function to isLargePrime(). The name would be just slightly weird, so that anyone using it would be intrigued enough to take a closer look.

\$\endgroup\$
  • \$\begingroup\$ "The name would be just slightly weird, so that anyone using it would be intrigued enough to take a closer look." Wells, I'm intrigued enough to take a closer look at this answer, so I guess this point is made??? \$\endgroup\$ – h.j.k. Jan 15 '15 at 10:12
12
\$\begingroup\$

If you want a combination of readability and performance, consider the following solution.

public class Primes {
    private final boolean[] isComposite;
    private int n = 2;

    public Primes(int sieveSize) {
        this.isComposite = new boolean[sieveSize];
    }

    public static int overestimateOfNthPrime(int n) {
        // http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
        return (int)(1.5 * n * Math.log(n));
    }

    public int next() {
        try {
            return n;
        } finally {
            // Sieve of Eratosthenes: mark multiples of n as composite
            for (int i = 2 * n; 0 <= i && i < this.isComposite.length; i += n) {
                this.isComposite[i] = true;
            }
            do {
               n++;     // TODO: check array bounds
            } while (this.isComposite[n]);
        }
    }

    public static long sumFirstPrimes(int n) {
        Primes primes = new Primes(overestimateOfNthPrime(n));
        long sum = 0;
        while (n-- > 0) {
            sum += primes.next();
        }
        return sum;
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        System.out.println(sumFirstPrimes(Integer.parseInt(args[0])));
        System.err.println(System.nanoTime() - start);
    }
}

If your concern is "people first", then I think this is an improvement. The sumFirstPrimes() function is more readable because the code that discovers more primes is decoupled from the code that sums them. There are no magic numbers like 5 and 6, and no weird special cases. Note that the readability comes mainly from the code structure, not from the comments on the code.

If your concern is performance, then the Sieve of Eratosthenes is a better algorithm for discovering many prime numbers. It doesn't matter how many ugly hacks you use to optimize your trial division method — the Sieve simply scales better (up to a point).

$$\begin{array}{r|r|r} \textrm{First } n \textrm{ primes} & \textrm{Legato's trial division} & \textrm{200_success's sieve} \\ \hline 10^3 & ~1000\ \mathrm{\mu s} & ~2000\ \mathrm{\mu s} \\ 10^4 & ~10\ \mathrm{ms} & ~10\ \mathrm{ms} \\ 10^5 & ~125\ \mathrm{ms} & ~40\ \mathrm{ms} \\ 10^6 & ~4000\ \mathrm{ms} & ~500\ \mathrm{ms} \\ 10^7 & \color{gray}{\textit{DNF}} & ~7\ \mathrm{s} \\ \end{array}$$

In the interest of full disclosure…

  • Making the estimate of the nth prime takes some mathematical knowledge.
  • I trust the estimate, so I didn't bother to check the array bounds.
  • For truly large problems (e.g 108), memory management for the Sieve would be a chore.
\$\endgroup\$
  • \$\begingroup\$ The memory management gets a little better if you use a java.util.BitSet instead of a boolean[] which as far as I can tell is about 16x more compact (1 bit for 1 bit in a BitSet, as opposed to 16 bits for a boolean[]. I don't know why it's 16, you'd think it'd be 8 at the most, but I find it to be 16 bits per element in a boolean array...) \$\endgroup\$ – corsiKa Jun 10 '15 at 21:04
  • \$\begingroup\$ Also as a side note, your use of n-- > 0 is deplorable considering the excellent opportunity to use the "goes to operator", namely n --> 0. ≈) \$\endgroup\$ – corsiKa Jun 10 '15 at 21:05
10
\$\begingroup\$

White space is your friend, particularly if you're focusing on "people friendly" code. (That's a noble goal by the way.)

    for (int i = 5; count < n; i += 2) {
        if (isPrime(i)) { result += i; count++; }
    }

Would be a little better as

    for (int i = 5; count < n; i += 2) {
        if (isPrime(i)) { 
            result += i; 
            count++; 
        }
    }

What's the difference? Not much to be honest. The win here is that each instruction is on its own line, hence easily understood to be two instructions, not one.

You also have commented out code in your isPrime method. Commented out code is dead code. Dead code is clutter. Remove clutter.

\$\endgroup\$
  • 1
    \$\begingroup\$ On the 'clutter', the idea was that adding it would prevent someone from mistaking it as a general primality test, and I commented those bits out so they could chose to port it as such elsewhere. If you still consider it clutter, in cases like these, should I rename the method to avoid confusion and/or specify it only works in this case or ? I've yet to work with a group, so I comment minimally, I'm really interested in developing a rule of thumb for cases like that. (I know this instance itself is simple, but speaking generally). \$\endgroup\$ – Legato Jan 15 '15 at 2:41
  • \$\begingroup\$ Regarding clutter, all functions have limitations, so I suggest (1) specify that num >= 4 in the function comment (doc string) (2)the commented out code is both distracting and likely to get out of date (3) make isPrime raise an exception if num < 4 (4) your colleague may not be as good at elementary number theory as you, so it is ok to cite a proof that it is ok to test every 6th integer as a factor. \$\endgroup\$ – dcorking Jan 15 '15 at 9:30
  • \$\begingroup\$ Consider this @Legato. What happens to those comments if someone like me comes behind you, sees "dead code" and deletes it without understanding that it was documentation? \$\endgroup\$ – RubberDuck Jan 15 '15 at 9:35
  • 1
    \$\begingroup\$ As for a general rule of thumb about when to leave comments, I'm going to cop out. That's holy war territory. (But I will say that I'm personally a minimalist.) I think the actual comments you left are good. I just don't like seeing commented out code. \$\endgroup\$ – RubberDuck Jan 15 '15 at 9:42

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.