Algoritmo da peneira de Eratóstenes: exemplo de Python, C++

A peneira de Eratóstenes é a peneira de números primos mais simples. É um algoritmo de números primos para pesquisar todos os números primos em um determinado limite. Existem várias peneiras de números primos. Por exemplo: a peneira de Eratóstenes, a peneira de Atkin, a peneira de Sundaram, etc.

A palavra "peneira”Significa um utensílio que filtra substâncias. Assim, o algoritmo de peneira em Python e outras linguagens referem-se a um algoritmo para filtrar números primos.

Este algoritmo filtra o número primo em uma abordagem iterativa. O processo de filtragem começa com o menor número primo. Um primo é um número natural maior que 1 e possui apenas dois divisores, viz., 1 e o próprio número. Os números que não são primos são chamados de números compostos.

Na peneira do método de Eratóstenes, um pequeno número primo é selecionado primeiro e todos os seus múltiplos são filtrados. O processo é executado em um loop em um determinado intervalo.

Por exemplo:

Vamos considerar o intervalo numérico de 2 a 10.

Algoritmo da Peneira de Eratóstenes

Após aplicar a peneira de Eratóstenes, produzirá a lista dos números primos 2, 3, 5, 7

Algoritmo da Peneira de Eratóstenes

Peneira do Algoritmo de Eratóstenes

Aqui está o algoritmo para a peneira de Eratóstenes:

Passo 1) Crie uma lista de números de 2 até o intervalo n fornecido. Começamos com 2 porque é o menor e primeiro número primo.

Passo 2) Selecione o menor número da lista, x (inicialmente x é igual a 2), percorra a lista e filtre os números compostos correspondentes marcando todos os múltiplos dos números selecionados.

Passo 3) Em seguida, escolha o próximo número primo ou o menor número não marcado da lista e repita a etapa 2.

Passo 4) Repita a etapa anterior até que o valor de x seja menor ou igual à raiz quadrada de n (x<=Peneira do Algoritmo de Eratóstenes).

Nota: O raciocínio matemático é bastante simples. O intervalo de números n pode ser fatorado como-

n=a*b

Novamente, n =Peneira do Algoritmo de Eratóstenes*Peneira do Algoritmo de Eratóstenes

= (fator menor que Peneira do Algoritmo de Eratóstenes) * (fator maior que Algoritmo da Peneira de Eratóstenes)

Então pelo menos um dos fatores principais ou ambos devem ser <=Peneira do Algoritmo de Eratóstenes. Assim, percorrendo até Peneira do Algoritmo de Eratóstenes Será suficiente.

Passo 5) Após essas quatro etapas, os números não marcados restantes seriam todos primos naquele intervalo n determinado.

Exemplo:

Vamos dar um exemplo e ver como funciona.

Para este exemplo, encontraremos a lista dos números primos de 2 a 25. Portanto, n=25.

Passo 1) Na primeira etapa, pegaremos uma lista de números de 2 a 25, pois selecionamos n=25.

Peneira do Algoritmo de Eratóstenes

Passo 2) Em seguida, selecionamos o menor número da lista, x. Inicialmente x=2 pois é o menor número primo. Em seguida, percorremos a lista e marcamos os múltiplos de 2.

Os múltiplos de 2 para o valor fornecido de n são: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Algoritmo da Peneira de Eratóstenes

Nota: A cor azul indica o número selecionado e a cor rosa indica os múltiplos eliminados

Passo 3) Em seguida, escolhemos o próximo menor número não marcado, que é 3, e repetimos o último passo marcando os múltiplos de 3.

Algoritmo da Peneira de Eratóstenes

Passo 4) Repetimos o passo 3 da mesma maneira até x=Algoritmo da Peneira de Eratóstenes ou 5.

Algoritmo da Peneira de Eratóstenes

Passo 5) Os restantes números não marcados seriam os números primos de 2 a 25.

Algoritmo da Peneira de Eratóstenes

Pseudo-código

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Exemplo de código C/C++ da peneira de Eratóstenes

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
} 

Saída:

2 3 5 7 11 13 17 19 23

Exemplo de programa Python da peneira de Eratóstenes

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Saída:

2
3
5
7
11
13
17
19
23

Peneira Segmentada

Vimos que o Crivo de Eratóstenes é necessário para percorrer todo o intervalo de números. Assim, é necessário O(n) espaço de memória para armazenar os números. A situação torna-se complicada quando tentamos encontrar números primos num intervalo enorme. Não é viável alocar um espaço de memória tão grande para um n maior.

O algoritmo pode ser otimizado introduzindo alguns novos recursos. A ideia é dividir o intervalo numérico em segmentos menores e calcular os números primos nesses segmentos, um por um. Esta é uma forma eficiente de reduzir o espaço complexcidade. Este método é chamado de peneira segmentada.

A otimização pode ser alcançada no seguintewing maneiras:

  1. Use uma peneira simples para encontrar números primos de 2 a Peneira Segmentada e armazene-os em uma matriz.
  2. Divida o intervalo [0…n-1] em vários segmentos de tamanho no máximo Peneira Segmentada
  3. Para cada segmento, itere através do segmento e marque o múltiplo de números primos encontrado na etapa 1. Esta etapa requer O(Peneira Segmentada) no máx.

A peneira regular requer O(n) espaço de memória auxiliar, enquanto a peneira segmentada requer O(Peneira Segmentada), o que é uma grande melhoria para um grande n. O método tem uma desvantagem também porque não melhora o tempo de comunicação.plexity.

ComplexAnálise de cidade

Espaço Complexidade:

O algoritmo de peneira simples de Eratóstenes requer O(n) espaço de memória. E a peneira segmentada exige
O(ComplexAnálise de cidade) espaço auxiliar.

Hora Complexidade:

A hora complexA qualidade de uma peneira regular do algoritmo de Eratóstenes é O(n*log(log(n))). O raciocínio por trás deste complexidade é discutida abaixo.

Para um determinado número n, o tempo necessário para marcar um número composto (isto é, números não primos) é constante. Portanto, o número de vezes que o loop é executado é igual a-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

A progressão harmônica da soma dos primos pode ser deduzida como log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Então, chegou a horaplexvai ser-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Assim chegou a horaplexcidade O(n * log(log(n)))

A seguir, você aprenderá sobre Triângulo de Pascal

Resumo

  • A peneira de Eratóstenes filtra os números primos em um determinado limite superior.
  • A filtragem de um número primo começa no menor número primo, “2”. Isso é feito iterativamente.
  • A iteração é feita até a raiz quadrada de n, onde n é o intervalo numérico fornecido.
  • Após essas iterações, os números que permanecem são os números primos.