Problemas no Crivo de Erastostenes

6 respostas
aajjbb

Ao implementar o crivo, que é o exercicio 7.27 do livro do Deitel 6ª edição, o enunciado é o seguinte:

a) Crie um array boolean de tipo primitivo com todos os elementos inicializados como true. Os elementos do array com indices primos permanecerão true. Todos os outros elementos do array por fim são configurados como false.

b) Iniciando com o indice de array 2, determine se um dado elemento é true. Se for, faça um loop pelo restante do array e configure como false se[size=18] cada elemento cujo indice é um multiplo do indice para o elemento com valor true[/size]. Entao continue o processo com o proximo elemento com valor true. Para o indice de array 2, todos os elementos alem do elemento 2 no array que tiverem indices multiplos de 2 (indices 4, 6, 8, 10 etc.) serão configurados como false; Quando esse processo for concluido, os elementos de array que ainda forem true indicam que o indice é um numero primo. Esses indices podem ser exibidos.

desenvolvi o seguinte codigo, mas nao estou interpretando bem a parte em negrito, tentei um operador ternario, mas minha logica esta erronea, alguem poderia me dar uma luz?

public class Crivo2 {

	boolean bool[];
	int primes[];

	public void findPrimes() {
		bool = new boolean[100];
		primes = new int[100];
		for (int i = 2; i < bool.length; i++) {
			bool[i] = true;
			if (bool[i] == true) {
				for (int j = 2; j < bool.length; j++) {
					if (bool[i] % bool[i] ? 0 : i == 0) {
						bool[i] = false;

					}
				}
			}
		}

	}

	public static void main(String[] args) {
		Crivo2 c = new Crivo2();
		c.findPrimes();
	}

}

6 Respostas

drsmachado

Você não precisa de 2 arrays, apenas um é suficiente.
Dentro do for, para cada elemento que seja múltiplo do index em questão (2, no caso), você altera para false. Quando o array termina, você volta e pega como index o próximo primo, no caso, 3 e assim sucessivamente…

aajjbb

é… mais meu problema é no if da linha 13 … e ja fiz umas alterações, nao to conseguindo ineterpretar bem essa parte…

aajjbb

eu fiz essa alteração no codigo, mas nao to conseguindo colocar no meu “if” apenas o indices dos elementos que sao true

E

Vamos lá, tio. Vou escrever uma coisa bem parecida, mas de jeito bem bobinho para você entender de uma vez por todas.

A primeira coisa é que você não precisa ter 2 arrays, um de inteiros e outro de booleans.
Você precisa de apenas um; a posição no array de booleans é que representa o número.
Por exemplo, para simbolizar que o número 13 é primo, é suficiente marcar a posição [13] como true.

A segunda coisa é que você precisa pensar um pouquinho, mas um pouquinho só. Vou dar um exemplo, e vou escrever de modo bem antigão (“estruturado” como se diz na faculdade).

public void acharPrimos() {
    int nElementos = 100;
    /* Crie um array boolean de tipo primitivo com todos os elementos inicializados como true. Os elementos do array com indices primos permanecerão true. Todos os outros elementos do array por fim são configurados como false. */
    boolean[] primos = new boolean[nElementos + 1]; // ou seja, o índice vai de 0 a 100
    for (int i = 0; i < primos.length; ++i) {
        primos[i] = true; // inicializando todos os elementos como true, conforme especificado
    }
    /* Iniciando com o indice de array 2, determine se um dado elemento é true. Se for, faça um loop pelo restante do array e configure como false se cada elemento cujo indice é um multiplo do indice para o elemento com valor true. Entao continue o processo com o proximo elemento com valor true. Para o indice de array 2, todos os elementos alem do elemento 2 no array que tiverem indices multiplos de 2 (indices 4, 6, 8, 10 etc.) serão configurados como false;  */
    int n = 2;
    while (n <= nElementos) {
        if (primos [n] == true) { // ou seja, se n é um valor primo...
            for (int i = 2 * n; i <= nElementos; i += n) {
                primos[i] = false; // aqui estou pegando 2 * n, 3 * n, 4 * n.... e marcando com false, para indicar que não é primo
            }
       } else {
           // Como n não é primo, temos de percorrer o array "primos" até achar um primo.
          n++;
       }
    }
    // Uma vez feito isso, vamos imprimir os valores a partir do 2:
    for (int i = 2; i < primos.length; ++i) {
        if (primos[i] == true) {
            System.out.println (i);
        }
    }        
}
E

Note que não há nenhum cálculo de resto nesse algoritmo. Não sei por que é que você está tentando usar “%”; não está escrito em lugar nenhum no enunciado da questão.

aajjbb

ah amigo, foi uma burrice aritimetica, isso era para poder definir o multiplo… obrigado.

Criado 24 de novembro de 2010
Ultima resposta 25 de nov. de 2010
Respostas 6
Participantes 3