5
\$\begingroup\$

This code works perfectly, but it bothers me. Having a labeled, nested for loop, with a true condition, a break statement, and a continue label...it really bothers me. But I couldn't figure out any other way to arrange the flow control here without sacrificing the efficiency. Any ideas?

private static ArrayList<Integer> primeList = new ArrayList<Integer>(Arrays.asList(2,3));

public static int getNextPrime() {
    int testNum;
    search:
        for (testNum = (primeList.get(primeList.size() - 1) + 2); true; testNum += 2) {
            int prime = 0;
            for (int index = 1; prime * prime <= testNum; index++) {
                prime = primeList.get(index);
                if (testNum % prime == 0) continue search;
            }
            break;
        }
    primeList.add(testNum);
    return testNum;
}

From the names I am using, this should be fairly self-documenting, but to say it in English: This is part of a public class Primes that I wrote, specifically the part that actually does the finding of primes. My various other methods (fillListToIndex, fillListToValue, findPrimeN—not shown) all ultimately rely on getNextPrime() for the actual primality testing.

All it does is find the next prime that has not already been found, memoize it, and return it.

\$\endgroup\$
5
\$\begingroup\$

Factor out the inner loop into a method (not just for the sake of structure, but because it is a method bool is_next_prime(int testNum)):

    for (...) {
        if (testNum % prime) == 0)
            return false;
    }
    return true;

Then

    int getNextPrime() {
        int testNum = primeList.get(primeList.size() - 1) + 2;
        while (!is_next_prime(testNum)) {
            testNum += 2;
        }
        return testNum;
    }
\$\endgroup\$
4
  • \$\begingroup\$ Beautiful. I knew there had to be a clean way to do it, I just couldn't see it. Fantastic. :) \$\endgroup\$ – Wildcard Oct 17 '15 at 0:46
  • \$\begingroup\$ @Wildcard Factoring out loops (aka no naked loops mantra) is an extremely useful technique. \$\endgroup\$ – vnp Oct 17 '15 at 0:47
  • \$\begingroup\$ Hmmm, there are only 3 results on Google for "no naked loops" and none of them are very helpful. Is there anywhere you can point me to learn that mantra (the concept, examples, etc.)? \$\endgroup\$ – Wildcard Oct 17 '15 at 0:56
  • 1
    \$\begingroup\$ @Wildcard Sorry it officially called "no raw loops"; watch this: channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning. It is C++, but the ideas are universal. \$\endgroup\$ – vnp Oct 17 '15 at 1:46
2
\$\begingroup\$

Instead of ending the inner for loop with your continue: statement when testNum %prime = 0, just make that part of the conditional of the inner for loop. That eliminates the need for continue statement (since there aren't any instructions after it anyway), the label, and of course the break statement gets eliminated by replacing true in the outer loop with testNum % prime != 0.

    public static int getNextPrime() {
        int testNum;
        // initialize prime so that the first time in loop testNum%prime!=0
        int prime = (primeList.get(primeList.size() - 1) + 2) + 1;
            for (testNum = (primeList.get(primeList.size() - 1) + 2); testNum % prime != 0; testNum += 2) 
            {

                prime = primeList.get(1);
                for (int index = 1; prime * prime <= testNum && testNum % prime != 0; index++) 
                {
                    prime = primeList.get(index);
                }

            }
        primeList.add(testNum);
        return testNum;
    }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Review! Good job on your first answer. \$\endgroup\$ – SirPython Oct 17 '15 at 1:16

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.