Problem with sieve of Eratosthenes - JAVA

3

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

Could anyone help me get the resolution of this exercise?

Follow the code as it is according to 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
    
asked by anonymous 09.11.2016 / 15:20

1 answer

4

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 these two loops, it was to use < instead of <= . By changing both by < , 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, then the algorithm fails due to overflow.

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

  

0 cousins found.

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

    
09.11.2016 / 17:54