Gerar Primos Erastótenes

Programação Java
#1

Tenho esse seguinte exercício,

[quote]Implemente a interface acima, para gerar números primos até um dado
número n, usando o crivo de Erastótenes:
Explicação do Algoritmo
Para exemplificálo,
vamos determinar a lista de números entre 1 e 30.

  • Inicialmente, determinase
    o maior número a ser checado. Ele
    corresponde à raiz quadrada do valor limite, arredondado para baixo. No
    caso, a raiz de 30, arredondada para baixo, é 5.
  • Crie uma lista de todos os números inteiros de 2 até o valor limite: 2
    3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30.
  • Encontre o primeiro número da lista. Ele é um número primo, 2.
  • Remova da lista todos os múltiplos do número primo encontrado. No
    nosso exemplo, a lista fica: 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29.
  • O próximo número da lista é primo. Repita o procedimento. No caso, o
    próximo número da lista é 3. Removendo seus múltiplos, a lista fica: 2 3 5 7
    11 13 17 19 23 25 29. O próximo número, 5, também é primo; a lista fica: 2 3
    5 7 11 13 17 19 23 29. 5 é o último número a ser verificado, conforme
    determinado inicialmente. Assim, a lista encontrada contém somente números
    primos.[/quote]

Consegui fazer isso

[code]public class Questao_01 {
public static boolean isPrimo(int numero) {
if (numero < 2)
return false;

    boolean result = true;
    double metade = numero / 2;
    for (double i = 2; i <= metade; i++) {
        if (numero % i == 0) {
            result = false;
            break;
        }
    }
    return result;
}

public static void main(String[]args) {
    for (int i = 0; i < 30; i++)
        if (isPrimo(i)) {
            System.out.println(i);
        }
}

}[/code]

O problema é que, o programa está imprimindo

[quote]3
5
7
11
13
17
19
23
29[/quote]

em vez de imprimir o que a questão pede, alguém pode me ajudar???

#2

A primeira coisa é que você não implementou o Crivo de Eratóstenes - então vai ter nota zero. Você criou um método que determina se um número é primo (que funciona para números pequenos, mas não para números grandes) mas não implementou o crivo.

#3

O Crivo precisa de um array. Tem algum array na sua solução?

#4

e como faço para implementar esse Crivo?

#5

KKKKK, ops

pessoal houve um “errinho” aqui, está certo o programa como pede o exercício, a questão é essa

[quote]Implemente a interface acima, usando como teste de primalidade o método
das divisões sucessivas, explicado abaixo:
O mais simples dos testes de primalidade consiste em dividir um número n por
todos os números inteiros que estiverem na faixa que vai de 2 até n 1.
Se
n for divisível por qualquer um deles, então n é um número composto. Caso
contrário, é um número primo"

Esqueci de postar essa parte , foi mal pessoal…

#6

Afinal qual a sua dúvida?

#7

Minha duvida é exatamente essa:

[quote]Implemente a interface acima, usando como teste de primalidade o método
das divisões sucessivas, explicado abaixo:
O mais simples dos testes de primalidade consiste em dividir um número n por
todos os números inteiros que estiverem na faixa que vai de 2 até n 1.
Se
n for divisível por qualquer um deles, então n é um número composto. Caso
contrário, é um número primo[/quote]

Me da uma força aí parceiro.

#8

Veja bem, você precisa limitar o for ao valor correspondente à raiz quadrada do mair número arredondado para baixo, certo?

Portanto, o for deveria ser limitado pelo valor dessa raiz…

#9

Mais o exercício pede que vá até o 30 mesmo, amigo, tem como me dar uma luz…

#10

Bom, acho que “Para exemplificálo,
vamos determinar a lista de números entre 1 e 30.” e “Implemente a interface acima, para gerar números primos até um dado
número n”, pra mim, significa que o exercício deve suportar qualquer número.
eu faria assim



        int valorMax = Integer.parseInt(JOptionPane.showInputDialog("Valor limite"));
        int raiz = 0;
        //modo tosco de descobrir a raiz:
        for (int r = 1; r < valorMax; r++) {
            if ((r * r) <= valorMax) {
                raiz = r;
            }
        }
        for(int g = 0; g <= raiz; g++){
            if(isPrimo(g)){
                System.out.println(""+g);
            }
        }
#11

[Removido]

#12

Porém existe um problema.
Eu acho que você não está sabendo direito como o Crivo funciona.
Bom vamos a lógica do problema.
Afinal como funciona o Crivo de Erastótenes?
Bem, pegue lápis e papel.

Como você quer 30 números teremos de calcular a raiz de 30.
Como ela não é exata, arredondamos para baixo ou chão, matemáticamente falando.
Você tem que ter um vetor com os valores de 2 até o limite em sequência.
2, 3, 4, 5, 6,…,30;
Vamos ler o vetor.
Opa! achamos um primo o 2.
Agora temos que varrer esse vetor procurando TODOS os múltiplos de 2.
Ao chegarmos em 30, temos de realocar esse vetor, ou seja, quando se encontra um múltiplo, por exemplo, você pode atribuir ao local o valor 0, assim fica fácil de achar os primos depois.
Vamos para o próximo número que não seja 0.
Opa! achamos o primo 3.
Agora temos que varrer esse vetor procurando TODOS os múltiplos de 3.
E assim por diante, até chegarmos ao número raiz, o 5;

Agora que conseguimos visualisar a proposta fica muito mais fácil.
Segue minha dica.
Sempre que tiver um problema, coloque-o no papel antes de qualquer coisa e organize a lógica. Apenas depois implemente.

Agora acredito que ficou muito mais fácil de fazer esse exercício.

Espero ter ajudado.
Abraço e boa sorte com o projeto.

#13

Estou aprendendo Python e li esse post. Aí resolvi implementar para treinar o crivo:

def crivo(n): n=int(n) li=range(2,n+1) primes=[] while len(li)>0: primes.append(li[0]) li=filter(lambda f: f%li[0]<>0,li) print primes

funcionou direitinho aki.

[]s

#14