Problem with Eratosthenes sieve - JAVA

Question

My teacher passed the following class for implementation of the Eratosthenes sieve, but gave very vague instructions on how we should do it, although he made it very clear that we should only touch the methods getPrimes() and findPrimes() and not in the rest of the code.

Could someone help me find a solution to this exercise?

Follow the code as per my best attempt at resolution:

package javaapplication1;

/**
 * Essa classe encontra numeros primos pelo metodo do
 * crivo de Eratostenes
 * 
 * @see java.lang.Object
 * @author 
 * @version 1.0
 */
public class Sieve
{   
    /** 
     * numero de primos encontrados
     */
    private int count = 0;

    /** 
     * arrays de primos (true se o numero i na posicao [i] eh primo)
     */
    private boolean[] primes;

    /**
     * O construtor define a quantidade maxima de numeros primos que serao
     * gerados pelo crivo de Eratostenes
     * 
     * @param size Define numero entre 0 e size-1 serao verificados 
     *             se sao primos ou nao
     */
    public Sieve(int size) 
    {
        primes = new boolean[ size ];
        // assumir, inicialmente, que todos numeros sao primos
        for ( int index = 0; index < primes.length; index++ )
        {   
            primes[ index ] = true;
        }
        // encontrar os numeros primos
        findPrimes();
    }

    /**
     * @return o numero de primos encontrados
     */
    public int getCount()
    {
        return count;
    }

    /**
     * @return array contendo true para os numeros que sao primos
     */
    public boolean [] getPrimes()
    {   // sua implementacao vem aui...
          return primes;
    }

    /**
     * Encontra primos pelo metodo do crivo de Eratostenes.
     * Ao final do metodo, o array primes contem true apenas para os 
     * numeros primos e count contem o numero de primos encontrados.
     */
    private void findPrimes()
    {   // sua implementacao vem aui...
             for(int i = 2; i <=primes.length; i++){
        if(primes[i]){
            for(int j = i; i*j <= primes.length; j++)
                primes[i*j] = false;
        }
    }
    }

    public static void main( String[] args )
    { 
      Sieve s = new Sieve( 16 );
      boolean[] p = s.getPrimes();
      for ( int index = 2; index < p.length; index++ )
         if ( p[ index ] )
            System.out.printf( "%d eh primo.\n", index );
      System.out.printf( "\n%d primos encontrados.\n", s.getCount() );
   } // end main

} // end class Sieve

Answer 1

Your algorithm is almost right. You just made a silly mistake in findPrimes():

         for(int i = 2; i <=primes.length; i++){

        for(int j = i; i*j <= primes.length; j++)

In those two ties, it was to use the < instead of <=. Exchanging both for <, your algorithm works and lists the prime numbers.

The algorithm works until you use new Sieve(46349). If you use new Sieve(46350) or a higher number, hence the algorithm fails due to overflow.

There is also the problem that in the end, the algorithm always shows this:

0 cousins found.

This is because nowhere are you putting one count++.