Crivo de Eratóstenes em Python & C++

O que é o Crivo de Eratóstenes?

O Crivo de Eratóstenes é o crivo de números primos mais simples. É um algoritmo usado para descobrir todos os números primos dentro de um limite dado. Existem vários crivos de números primos, incluindo o Crivo de Eratóstenes, o Crivo de Atkin e o Crivo de Sundaram.

A palavra "peneira"Refere-se a um utensílio que filtra substâncias. Da mesma forma, o algoritmo de peneira em Python e outras linguagens se refere a um método que filtra números primos de uma lista de números inteiros.

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

Por que usar o Crivo de Eratóstenes?

No método do Crivo 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 intervalo dado, produzindo todos os números primos até n de forma eficiente, sem realizar divisões de tentativa em cada candidato.

Isso torna o crivo mais rápido do que verificar a primalidade de um número por vez. É amplamente utilizado em teoria dos números, criptografia, hashing e programação competitiva, onde muitos números primos precisam ser gerados rapidamente.

Por exemplo:

Vamos considerar o intervalo de números de 2 a 10.

Após aplicar o Crivo de Eratóstenes, será obtida a lista de números primos 2, 3, 5 e 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 dado. Começamos com 2 porque é o menor e o 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 do número selecionado.

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 o passo anterior até que o valor de x seja menor ou igual à raiz quadrada de n (x <=).

Observação: 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 <= Portanto, percorrendo até Será suficiente.

Passo 5) Após esses quatro passos, os números restantes não marcados serão todos os números primos naquele intervalo n.

Exemplo trabalhado

Exemplo:

Vejamos um exemplo e como funciona.

Neste exemplo, vamos encontrar a lista de números primos de 2 a 25. Portanto, n = 25.

Passo 1) Na primeira etapa, vamos pegar uma lista de números de 2 a 25, já que selecionamos n = 25.

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

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

Observação: 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 forma até que x = ou 5.

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

Pseudo-Code

O pseudocódigo a seguir captura a estrutura básica do Crivo de Eratóstenes antes de traduzi-lo para o código propriamente dito.

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++ Code Exemplo

Abaixo segue uma lista completa. C++ Implementação do Crivo de Eratóstenes que imprime todos os números primos até um limite superior escolhido.

#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

Os seguintes Python O programa implementa o mesmo algoritmo usando uma lista booleana e um laço while.

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 percorre toda a extensão dos números. Portanto, ele precisa de espaço de memória O(n) para armazenar os números. A situação se complica quando tentamos encontrar números primos em uma extensão muito grande, pois não é viável alocar um bloco 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 pelo segmento e marque os múltiplos dos números primos encontrados na etapa 1. Esta etapa requer O() no máximo.

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

Análise de Complexidade

Compreender a complexidade espacial e temporal ajuda a escolher entre a peneira regular e a peneira segmentada para um determinado tamanho de problema.

Complexidade do espaço:

O algoritmo simples do Crivo de Eratóstenes requer espaço de memória O(n). O crivo segmentado requer O() espaço auxiliar.

Complexidade de tempo:

A complexidade temporal de um algoritmo regular do Crivo de Eratóstenes é O(n*log(log(n))). O raciocínio por trás dessa complexidade é discutido abaixo.

Para um dado número n, o tempo necessário para marcar um número composto (isto é, um número não primo) é 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 números primos pode ser deduzida como log(log(n)):

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

Assim, a complexidade temporal será:

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

= n * log(log(n))

Assim, a complexidade de tempo é O(n * log(log(n))).

Em seguida, você aprenderá sobre Triângulo de Pascal.

Perguntas Frequentes