Source: "Agile Software Development: Principles, Patterns, and Practices" by Robert C. Martin. Available at www.objectmentor.com/PPP.

Initial code for refactoring:



/**
 * This class Generates prime numbers up to a user specified maximum.
 * the algorithm used is the Sieve of Eratosthenes.
 * 

* Eratosthenes of Cyrene, b. c. 276 BC, Cyrene, Libya -- * d. c. 194, Alexandria. The first man to calculate the circumference * of the Earth. Also known for working on calendars with leap * years and ran the library at Alexandria. *

* The algorithm is quite simple. Given an array of integers starting * at 2. Cross out all multiples of 2. Find the next uncrossed * integer, and cross out all of its multiples. Repeat until * you have passed the square root of the maximum value. * * @author Robert C. Martin * @version 9 Dec 1999 rcm */ import java.util.*; /** * Class declaration * * * @author Robert C. Martin * @version %I%, %G% */ public class GeneratePrimes { /** * @param maxValue is the generation limit. */ public static int[] generatePrimes(int maxValue) { if (maxValue >= 2) // the only valid case { // declarations int s = maxValue + 1; // size of array boolean[] f = new boolean[s]; int i; // initialize array to true. for (i = 0; i < s; i++) f[i] = true; // get rid of known non-primes f[0] = f[1] = false; // sieve int j; for (i = 2; i < Math.sqrt(s) + 1; i++) { for (j = 2 * i; j < s; j += i) f[j] = false; // multiple is not prime } // how many primes are there? int count = 0; for (i = 0; i < s; i++) { if (f[i]) count++; // bump count. } int[] primes = new int[count]; // move the primes into the result for (i = 0, j = 0; i < s; i++) { if (f[i]) // if prime primes[j++] = i; } return primes; // return the primes } else // maxValue < 2 return new int[0]; // return null array if bad input. } }


Test case:

import junit.framework.*;
import java.util.*;

public class TestGeneratePrimes extends TestCase
{
  public TestGeneratePrimes(String name)
  {
    super(name);
  }

  public void testPrimes()
  {
    int[] nullArray = GeneratePrimes.generatePrimes(0);
    assertEquals(nullArray.length, 0);

    int[] minArray = GeneratePrimes.generatePrimes(2);
    assertEquals(minArray.length, 1);
    assertEquals(minArray[0], 2);

    int[] threeArray = GeneratePrimes.generatePrimes(3);
    assertEquals(threeArray.length, 2);
    assertEquals(threeArray[0], 2);
    assertEquals(threeArray[1], 3);

    int[] centArray = GeneratePrimes.generatePrimes(100);
    assertEquals(centArray.length, 25);
    assertEquals(centArray[24], 97);
  }
}

Refactored code:



/**
 * This class Generates prime numbers up to a user specified
 * maximum.  The algorithm used is the Sieve of Eratosthenes.
 * Given an array of integers starting at 2:
 * Find the first uncrossed integer, and cross out all its
 * multiples.  Repeat until there are no more multiples
 * in the array.
 */

public class PrimeGenerator
{
  private static boolean[] crossedOut;
  private static int[] result;

  public static int[] generatePrimes(int maxValue)
  {
    if (maxValue < 2)
      return new int[0];
    else
    {
      uncrossIntegersUpTo(maxValue);
      crossOutMultiples();
      putUncrossedIntegersIntoResult();
      return result;
    }
  }

  private static void uncrossIntegersUpTo(int maxValue)
  {
    crossedOut = new boolean[maxValue + 1];
    for (int i = 2; i < crossedOut.length; i++)
      crossedOut[i] = false;
  }

  private static void crossOutMultiples()
  {
    int limit = determineIterationLimit();
    for (int i = 2; i <= limit; i++)
      if (notCrossed(i))
        crossOutMultiplesOf(i);
  }

  private static int determineIterationLimit()
  {
    // Every multiple in the array has a prime factor that
    // is less than or equal to the root of the array size,
    // so we don't have to cross of multiples of numbers
    // larger than that root.
    double iterationLimit = Math.sqrt(crossedOut.length);
    return (int) iterationLimit;
  }

  private static void crossOutMultiplesOf(int i)
  {
    for (int multiple = 2*i;
         multiple < crossedOut.length;
         multiple += i)
      crossedOut[multiple] = true;
  }

  private static boolean notCrossed(int i)
  {
    return crossedOut[i] == false;
  }

  private static void putUncrossedIntegersIntoResult()
  {
    result = new int[numberOfUncrossedIntegers()];
    for (int j = 0, i = 2; i < crossedOut.length; i++)
      if (notCrossed(i))
        result[j++] = i;
  }

  private static int numberOfUncrossedIntegers()
  {
    int count = 0;
    for (int i = 2; i < crossedOut.length; i++)
      if (notCrossed(i))
        count++;

    return count;
  }
}


import junit.framework.*;

public class TestGeneratePrimes extends TestCase
{
  public static void main(String args[])
  {
      junit.swingui.TestRunner.main(
        new String[] {"TestGeneratePrimes"});
  }
  public TestGeneratePrimes(String name)
  {
    super(name);
  }

  public void testPrimes()
  {
    int[] nullArray = PrimeGenerator.generatePrimes(0);
    assertEquals(nullArray.length, 0);

    int[] minArray = PrimeGenerator.generatePrimes(2);
    assertEquals(minArray.length, 1);
    assertEquals(minArray[0], 2);

    int[] threeArray = PrimeGenerator.generatePrimes(3);
    assertEquals(threeArray.length, 2);
    assertEquals(threeArray[0], 2);
    assertEquals(threeArray[1], 3);

    int[] centArray = PrimeGenerator.generatePrimes(100);
    assertEquals(centArray.length, 25);
    assertEquals(centArray[24], 97);
  }

  public void testExhaustive()
  {
    for (int i = 2; i < 500; i++)
        verifyPrimeList(PrimeGenerator.generatePrimes(i));
  }

  private void verifyPrimeList(int[] list)
  {
    for (int i=0; i < list.length; i++)
        verifyPrime(list[i]);
  }

  private void verifyPrime(int n)
  {
    for (int factor=2; factor < n; factor++)
      assert(n%factor != 0);
  }
}

This is an example from CSci 3601 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.