Sieve of Eratosthenes (min and max)

Question

I am using the Sieve of Eratosthenes algorithm to find the prime numbers in a range (from a min value to a max value). However, I cannot seem to get it to work if I include a min value.

Here is my code in Java:

  protected static List<Integer> getSievePrimes(int a, int b) {
    List<Integer> primeNumbers = new ArrayList();

    boolean [] isComposite = new boolean [b + 1];
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= b; i++) {
//    for (int i = a == 1 ? 2 : a; i <= b; i++) {
        if (!isComposite[i]) {
            // 'i' is a prime number
            //if (i >= a) {
                primeNumbers.add(i);
            //}
            int multiple = 2;
            while (i * multiple <= b) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return primeNumbers;
  }

As you can see it currently only caters for the max value (b), and not the min value (a).

Question

How can I modify the method above to cater for both min and max?

See my answer [here](https://stackoverflow.com/a/10249801/448810). — user448810, Jan 16 '18 at 20:51
You would find the first index `i` in `primeNumbers` such that `primeNumbers[i] >= a`, and then return the subarray `primeNumbers[i]...primeNumbers[primeNumbers.length-1]` using something like `Arrays.copyOf()`. Or you can suppress adding a prime number unless it is >= `a'. — President James K. Polk, Jan 17 '18 at 13:23
starting at a min value causes false positives. for example min 1000 and max 1003 will identify 1000, 1001, 1002, and 1003 as primes. — DwB, Jan 17 '18 at 13:42

score 0 · Answer 1 · edited Nov 12 '18 at 08:22

public boolean isPrime( int test ) 
{

  int k;

  if( test < 2 )
    return false;
  else if( test == 2 )  
    return true;
  else if( ( test > 2 ) && ( test % 2 == 0 ) )
    return false;
  else
  {
    for( k = 3; k < ( test/2 ); k += 2 )
    {
        if( test % k == 0 ) 
            return false;
    }
  }

  return true;
}

public void sieveOfEratosthenes( int first, int last )
{
  boolean[ ] sieve = new boolean[ ( last - first ) + 1 ];

  int count = 0;
  int index = 0;

  int cursor = first;
  int end = last;

  while( cursor <= end )
  {
     if( isPrime( cursor ) != sieve[ index ] )
     {
        System.out.println( cursor+" " );
        count++;
     }

     cursor++;
     index++;
  }

  cursor = first;

  if( count == 0 )
     System.out.println( "There are "+count+" primes from "+cursor+" to "+end+"." );
  else if( count == 1 )
     System.out.println( "is the "+count+" prime from "+cursor+" to "+end+"." );
  else
     System.out.println( "are the "+count+" primes from "+cursor+" to "+end+"." );
}

For readability, I implemented my isPrime( i ) method apart from the sieveOf Eratosthenes( x, y ) method. Both are succinct, as result, not to mention that they both work as intended. Cheers! — user2710322, Feb 02 '18 at 18:31

Sieve of Eratosthenes (min and max)

1 Answers1