import java.util.ArrayList;
import java.util.Arrays;

public class PrimeNumbers {

    /**
     * Returns the prime numbers between nMin (included) and nMax (included)
     * @param nMin
     * @param nMax
     * @return
     */
    public Integer[] between(Integer nMin, Integer nMax) {
        if (nMin < 1)   {   //make sure nMin is not less than 1
            nMin = 1;
        }
        if (nMax < nMin) {
            return new Integer[0];
        }

        return primeNumbersFrom1ToN(nMin,  nMax);
    }


    private Integer[] primeNumbersFrom1ToN(Integer min, Integer max) {
        boolean[] prime = new boolean[max+1];
        Arrays.fill(prime, true);

        for (int counter = 2; counter <= max; counter ++) {
            if (prime[counter]) {
                markMultiplesAsNotPrime(counter, max, prime);
            }
        }
        return extractPrimesFromArray(prime, min, max);
    }

    private void markMultiplesAsNotPrime(Integer basePrime, Integer max, boolean[] prime) {
        for (int multiplier = 2; basePrime * multiplier <= max; multiplier++) {
            prime[basePrime * multiplier] = false;
        }
    }

    private Integer[] extractPrimesFromArray(boolean[] prime, Integer min, Integer max) {
        ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
        for (int number = min; number <= max; number++) {
            if(prime[number]) {
                primeNumbers.add(number);
            }
        }
        return primeNumbers.toArray(new Integer[primeNumbers.size()]);
    }


}


/* Test follows */


import junit.framework.Assert;
import org.junit.Test;

public class PrimeNumbersTest {

    @Test
    public void primeNumberGeneratorReturnsSomething() {
        Assert.assertNotNull(new PrimeNumbers().between(1,1));
    }


    @Test
    public void primeNumberGeneratorWorksWith1() {
        Integer[] arrayOfOne = new PrimeNumbers().between(1, 1);
        Assert.assertEquals(1, arrayOfOne.length);
        Assert.assertEquals(1, arrayOfOne[0].intValue());
    }

    @Test
    public void primeNumberGeneratorWorksWith3() {
        Integer[] arrayOfOne = new PrimeNumbers().between(1, 10);
        Assert.assertEquals(5, arrayOfOne.length);
        Assert.assertEquals(1, arrayOfOne[0].intValue());
        Assert.assertEquals(2, arrayOfOne[1].intValue());
        Assert.assertEquals(3, arrayOfOne[2].intValue());
        Assert.assertEquals(5, arrayOfOne[3].intValue());
        Assert.assertEquals(7, arrayOfOne[4].intValue());
    }

    @Test
    public void primeNumberGeneratorWorksWithInterval() {
        Integer[] arrayOfOne = new PrimeNumbers().between(6, 23);
        Assert.assertEquals(6, arrayOfOne.length);
        Assert.assertEquals(7, arrayOfOne[0].intValue());
        Assert.assertEquals(11, arrayOfOne[1].intValue());
        Assert.assertEquals(13, arrayOfOne[2].intValue());
        Assert.assertEquals(17, arrayOfOne[3].intValue());
        Assert.assertEquals(19, arrayOfOne[4].intValue());
        Assert.assertEquals(23, arrayOfOne[5].intValue());
    }

    @Test
    public void doesntBreakWithNegativeMin() {
        Integer[] arrayOfOne = new PrimeNumbers().between(-100, 10);
        Assert.assertEquals(5, arrayOfOne.length);
    }

    @Test
    public void doesntBreakWithNegativeMax() {
        Integer[] arrayOfOne = new PrimeNumbers().between(1, -10);
        Assert.assertEquals(0, arrayOfOne.length);
    }

    @Test
    public void doesntBreakWithMinAndMaxNegative() {
        Integer[] arrayOfOne = new PrimeNumbers().between(-100, -10);
        Assert.assertEquals(0, arrayOfOne.length);
    }

    @Test
    public void returnsEmptyWhenMaxIsLessThanMin() {
        Integer[] arrayOfOne = new PrimeNumbers().between(100, 10);
        Assert.assertEquals(0, arrayOfOne.length);
    }
}