Peneira de eratóstenes com c ++

Um número primo é um número natural (inteiro) que é maior ou igual a dois, que só pode ser dividido por si mesmo e 1. Os primeiros números primos são: 2, 3, 5, 7, etc.

Para o número 5, o número de números primos que estão até e/ou incluindo 5 são:

2, 3, 5

Para o número 8, o número de números primos que estão até e/ou incluindo 8 são:

2, 3, 5, 7

Para o número 19, o número de números primos que estão até e/ou incluindo 19 são:

2, 3, 5, 7, 11, 13, 17, 19

Para o número 25, o número de números primos que estão até e/ou incluindo 25 são:

2, 3, 5, 7, 11, 13, 17, 19, 23

Para o número 36, o número de números primos que estão até e/ou incluindo 36 são:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Para o número 37, o número de números primos que estão até e/ou incluindo 37 são:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37

Essas listas são apenas exemplos. Existem muitas outras listas de exemplos de números primos abaixo e/ou incluindo um determinado número. Comece a compreensão da peneira dos eratóstenos, observando que os números primos abaixo de um número menor é o mesmo que a primeira parte dos números primos abaixo de um dado número maior.

A peneira dos eratóstenos é uma técnica para encontrar todos os números primos que são menores ou iguais a um determinado número, como 36 ou 37 acima. Esse número como 36 ou 37 geralmente recebe o nome da variável "n" na programação. A peneira de eratóstenes é considerada um algoritmo eficiente para obter a lista de números primos.

Demonstração para peneira de eratóstenes

A questão é: encontre os números primos menores ou iguais a 5, por exemplo, de uma maneira eficiente. A maneira eficiente aqui significa usar o mínimo de operações possível. Os números primos começam de 2. Todos os números, incluindo os múltiplos de pequenos números primos de 2 a 5, são:

2, 3, 4, 5

Nesse intervalo, um número que não é um número primo é um múltiplo de um número primo anterior. Um múltiplo pode ser obtido pela adição do mesmo número primo, repetidamente. Por exemplo, 2 + 2 é 4, mais 2 novamente é 6. E isso continua além do alcance. Quatro, que é um múltiplo de 2, não deve estar na lista porque não é um número primo. A equação 3 + 3 é 6, que já está além do intervalo. E 6 ou qualquer número além do intervalo não deve estar na lista. Então, o resultado é o seguinte:

2, 3, 5

O número em questão aqui é 5. A raiz quadrada de 5 é 2.24. O valor inteiro para a raiz quadrada de 5 é 2. Os múltiplos de números primos abaixo e até 2, que é o valor inteiro da raiz quadrada de 5, são removidos da lista de todos os números.

Considere agora, o número 8. Todos os números, incluindo os múltiplos de pequenos números primos de 2 a 8, são:

2, 3, 4, 5, 6, 7, 8

A equação 2 + 2 é 4. Quatro sai. A equação 4+2 é 6. Seis sai. A equação 6 + 2 é 8. Oito está fora. O próximo número primo a considerar é 3. A equação 3 + 3 é 6. Seis já estão descartados pela adição contínua de 2. A equação 6 + 3 é 9; que está fora de alcance. Os números primos entre 2 e 8, inclusive, são:

2, 3, 5, 7

O número em questão aqui é 8. A raiz quadrada de 8 é 2.83. O valor inteiro para a raiz quadrada de 8 é 2. Os múltiplos dos números primos abaixo e até 2, que é o valor inteiro da raiz quadrada de 8 são removidos para obter a lista necessária de números primos.

Um problema semelhante é listar os números primos de 2 a 19, inclusivamente. Todos os números de 2 a 19, inclusive são:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 19

A equação 2 + 2 é 4; 4 está fora. A equação 4 + 2 é 6; 6 está fora. A equação 6 + 2 é 8; 8 está fora. A equação 8 + 2 é 10; 10 está fora. A equação 10 + 2 é 12; 12 está fora. A equação 12 + 2 é 14; 14 está fora. A equação 14 + 2 é 16; 16 está fora. A equação 16 + 2 é 18; 18 está fora. A equação 18 + 2 é 20, que está acima da faixa; 20 está fora.

O próximo número primo a considerar, subindo para a raiz quadrada de 19, é 3. A equação 3 + 3 é 6; 6 já está descartado como um múltiplo de 2. A equação 6 + 3 é 9; 9 sai. A equação 9 + 3 é 12; 12 já está descartado como um múltiplo de 2. A equação 12 + 3 é 15; 15 está fora. A equação 15 + 3 é 18; 18 já está descartado como um múltiplo de 2. A equação 18 + 3 é 21, que está acima da faixa. O resultado é:

2, 3, 5, 7, 11, 13, 17, 19

O número em questão aqui é 19. A raiz quadrada de 19 é 4.36. O valor inteiro para a raiz quadrada de 19 é 4. Os múltiplos de números primos abaixo e até 4, que é o valor inteiro da raiz quadrada de 19 são removidos.

Os números primos abaixo e até 4 são: 2 e 3. Devido a 3, não havia sentido em remover os números 6, 12 e 18 que são múltiplos de 3, que já são removidos como múltiplos de 2. Somente os múltiplos de 3 que não são múltiplos de 2 são removidos por causa de 3. Na prática, depois de remover os múltiplos de 2, apenas os múltiplos de e acima de 3 x 3 = 9 devem ser removidos sem repetir a remoção de 6. Por causa de 3, os números a serem removidos são 9, 12, 15 e 18; com 12 e 18 removidos duas vezes em teoria. O número 6 deve ser removido uma vez e não duas vezes.

Seja n 25, um novo número em questão. Todos os números de 2 a 25 são:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 23, 24, 25

A equação 2 + 2 é 4; 4 sai. A equação 4 + 2 é 6; 6 está fora. A equação 6 + 2 é 8; 8 está fora. A equação 8 + 2 é 10; 10 está fora. A equação 10 + 2 é 12; 12 está fora. A equação 12 + 2 é 14; 14 está fora. A equação 14 + 2 é 16; 16 está fora. A equação 16 + 2 é 18; 18 está fora. A equação 18 + 2 é 20; 20 está fora. A equação 20 + 2 é 22; 22 está fora. A equação 22 + 2 é 24; 24 está fora. A equação 24 + 2 é 26, que está acima do intervalo.

O próximo número primo a considerar, subindo em direção à raiz quadrada de 25, é 3. A equação 3 + 3 é 6; 6 já está descartado como um múltiplo de 2. A equação 6 + 3 é 9; 9 sai. A equação 9 + 3 é 12. Doze já estão descartados como um múltiplo de 2. A equação 12 + 3 é 15; 15 está fora. A equação 15 + 3 é 18; 18 já está descartado como um múltiplo de 2. A equação 18 + 3 é 21; 21 sai. A equação 21 + 3 é 24; 24 já está descartado como um múltiplo de 2. A equação 24 + 3 é 27, que está acima da faixa.

O próximo número primo a considerar, subindo em direção à raiz quadrada de 25, que é 5, é 5. A equação 5 + 5 é 10; 10 já está descartado como um múltiplo de 2. A equação 10 + 5 é 15; 15 já está descartado como um múltiplo de 3. A equação 15 + 5 é 20; 20 já está descartado como um múltiplo de 2. A equação 20 + 5 é 25; 25 sai. O resultado é:

2, 3, 5, 7, 11, 13, 17, 19, 23

O número em questão aqui é 25. A raiz quadrada de 25 é 5. O valor inteiro para a raiz quadrada de 25 é 5. Os múltiplos de números primos abaixo e até 5, que é o valor inteiro da raiz quadrada de 25, são removidos.

Os números primos abaixo e até 5 são 2, 3 e 5. Devido a 2, os números que devem ser removidos da lista de todos os números por múltiplos são: 4, 6, 8, 10, 12, 14, 16, 18, 18, 20, 22 e 24. Devido a 3, os números que devem ser removidos da lista por múltiplos são: 6, 9, 12, 15, 18, 21 e 24. Devido a 5, os números que devem ser removidos por múltiplos são: 10, 15, 20 e 25.

Por todos os múltiplos, as remoções são as seguintes:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 6, 9, 12, 15, 18, 21, 24

5: 10, 15, 20, 25

Por múltiplos, 6 é removido duas vezes (em teoria), 10 é removido duas vezes (em teoria), 12 é removido duas vezes (em teoria), 15 é removido duas vezes (em teoria), 20 é removido duas vezes (em teoria) e 24 é removido duas vezes (em teoria).

No entanto, se devido a 3, a remoção começa de 3 x 3 = 9, então 6 é removido apenas uma vez uma vez. Se devido a 5, a remoção começa de 5 x 5 = 25, então a remoção de 10, 15 e 20 é feita uma vez cada. No entanto, a remoção de 12, 18 e 24 ainda é feita duas vezes por número. Ainda assim, haveria alguma vantagem, pois quatro operações repetidas de remoção são omitidas (para 6, 10, 15 e 20). Isso melhora a eficiência (complexidade do tempo). Com isso, as remoções serão:

2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24

3: 9, 12, 15, 18, 21, 24

5: 25

Os números 6, 10, 15 e 20 foram removidos uma vez, em vez de duas vezes. Os números, 12, 18 e 24 foram removidos duas vezes. A partir de agora, nada pode ser feito para remover 12, 18 e 24 apenas uma vez.

As situações para os números 36 e 37, ou qualquer outro número maior que 1, são explicados da mesma forma.

Evitando redundância

Apenas removendo os múltiplos de números primos de 2 para o valor inteiro de √n, o conjunto necessário de números primos é obtido. A eficiência pode ser melhorada removendo os múltiplos de números primos, começando do quadrado do número primário (i²) até o valor inteiro de √n como sugerido anteriormente. Isso omite algumas operações de remoção de números. Então, reduzindo o número total de operações. A peneira dos eratóstenos é feita por esta segunda abordagem.

Algoritmo de peneira de eratóstenos

O algoritmo começa criando um vetor indexado à base de zero de comprimento que é n+1. Cada elemento deste vetor é inicializado para booleano, verdadeiro, exceto o primeiro e o segundo elementos para o índice 0 e o índice 1 que são inicializados para falsos. Para este vetor, o índice 2 corresponde ao número (Prime) 2; O índice 3 corresponde ao número (Prime) 3; O índice 4 corresponde ao número 4; e assim por diante. Como o vetor é zero um índice baseado, o comprimento deve ser n+1 para que o último índice corresponda a n.

Um número de índice para esta lista de vetores que deve ser removida não é removida em si: o valor do número do índice é feito falso para indicar a remoção. Isto é, o elemento recebe o valor falso. Portanto, se um número (índice) deverá ser removido da lista (vetor) mais de uma vez, o valor para o índice é falso mais de uma vez.

No final, os índices para os elementos do vetor cujos valores permaneceram verdadeiros são lidos como os números primos.

Antes disso, os múltiplos de índices primários começando a partir do quadrado do índice principal (i²) até o valor inteiro de √n são marcados como falsos.

Codificação C ++

O programa em C ++ deve começar com o seguinte:

#incluir
#incluir
usando namespace std;

A peneira da função Eratóstenes é a seguinte:

vetor peneira (int n)
vetor peneira (n+1, verdadeiro);
peneira [0] = false;
peneira [1] = false;
int i = 2;
enquanto (eu * eu <= n)
if (peneira [i] == true) // se eu for o número primo
int j = i * i;
enquanto (j <= n) //marking multiples with false
peneira [j] = false;
j = j + i; // incremento em múltiplos


i = i + 1; // Incremento normal do loop externo, por 1

Retornar peneira;

Leia os comentários do código. O nome da função é Sieve (). O vetor retornado, depois que todos os múltiplos são marcados como falsos, também é chamado de peneira. Uma função principal C ++ adequada para este código é:

int main (int argc, char ** argv)

vetor vtr = peneira (37);
para (int i = 0; iif (vtr [i] == true)
cout << i << ";
cout << endl;
retornar 0;

Com este código, a saída é a seguinte:

2 3 5 7 11 13 17 19 23 29 31 37

A complexidade do tempo para esta função é O (n log n).

Conclusão

O algoritmo começa fazendo um vetor indexado à base de zero do comprimento n+1. Cada elemento deste vetor é inicializado para booleano, verdadeiro, exceto o primeiro e o segundo elementos para o índice 0 e o índice 1 que são inicializados para falsos. Para este vetor, cada índice é um número de interesse. Como o vetor é indexado à base de zero, o comprimento deve ser n+1 para que o último índice seja n.

O valor do número que é o índice é feito falso para indicar a remoção. Isto é, o elemento recebe o valor falso.

No final, os índices para os elementos do vetor cujos valores permaneceram verdadeiros são lidos como os números primos.

Antes disso, os múltiplos de índices primos começando do quadrado do índice principal até o valor inteiro de √n são marcados como falsos.