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

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, a saber, 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.

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

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<=).

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

n=a*b

Novamente, n =*

= (fator menor que ) * (fator maior que )

Então pelo menos um dos fatores principais ou ambos devem ser <=. Assim, percorrendo até 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.

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.

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.

Passo 4) Repetimos o passo 3 da mesma maneira até x= ou 5.

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

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

Peneira de Eratóstenes C/C++ exemplo de código

#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

Peneira de Eratóstenes Python Exemplo de programa

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 a complexidade do espaço. Este método é chamado de peneira segmentada.

A otimização pode ser alcançada da seguinte maneira:

1. Use uma peneira simples para encontrar números primos de 2 a e armazene-os em uma matriz.
2. Divida o intervalo [0…n-1] em vários segmentos de tamanho no máximo
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() no máx.

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

Análise de Complexidade

Complexidade do espaço:

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

Complexidade de tempo:

A complexidade de tempo de um algoritmo de peneira regular de Eratóstenes é O(n*log(log(n))). O raciocínio por trás dessa complexidade é discutido 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, a complexidade do tempo será-

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

= n * log(log(n))

Assim, a complexidade do tempo 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.